Purely functional data structure

In computer science, a purely functional data structure is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable. This restriction ensures that the data structure possesses the advantages of immutable objects: (full) persistency, quick copy of objects, and thread safety. Efficient purely functional data structures may require the use of lazy evaluation and memoization.

Purely functional data structures are often represented in a different way than their imperative counterparts. For example, an array with constant-time access and update is a basic component of most imperative languages. Many imperative data structures, such as the hash table and binary heap, are based on arrays. An array can be replaced by a map or random access list, which admits a purely functional implementation, but access and update operations may run in logarithmic time. Purely functional data structures can be implemented in imperative and object-oriented languages, but their time and/or space performance may be inferior to that of data structures lacking purely functional properties.

A data structure is never inherently functional. For example, a stack can be implemented as a singly-linked list. This implementation is purely functional as long as the only operations on the stack return a new stack without altering the old stack. However, if the language is not purely functional, the run-time system may be unable to guarantee immutability.

...
Wikipedia