What are Functional data structures?

[Hussein Baghdadi]

Hi,
What does a functional data structure mean (being persisted and lazy or something else)?
Do functional languages have their own data structures (other than the structures we already know like maps, sets, graphs ...)?
Thanks.

[Chris Houser]

A function data structure is one that doesn't support destructive updates, that is you can't change a value in the structure itself but instead create a new structure with your "change" applied to it. In order to do this efficiently, that is without copying the entire collection each time a "change" is made", a variety of techniques are used, including structural sharing (the new collection keeping a reference to part of the old collection) and laziness (not computing the exact details of some part of the structure until they're needed).

Persistent collections are the subset of functional collections whose performance does not degrade as you create newer and newer versions. That means it's safe and efficient for one part of your code to keep and use a collection while some other part starts with that collection and makes a series of "changes" to it, ending up with a very different new collection of it's own. Not all functional data structures can do this, but persistent ones can.

Functional languages generally provide functional versions of collection types you're already familiar with. Clojure provides persistent versions of maps (a.k.a. associative arrays) both sorted and hashed, as well as sets (sorted and hashed), vectors, lists, and queues.

[Hussein Baghdadi]

Thanks for the detailed explanation, highly appreciated.
Is it possible to achieve laziness with non functional data structures?
Also, given a functional data structure is different from non functional one, does this effects the algorithms too?

[Chris Houser]

I think mutable data structures are less likely to need laziness internally in order to achieve their desired performance. On the other hand, laziness at it's core is just delayed execution, which is fairly simple to build in any language that supports closures. It would be possible, for example, to build a lazy seq like Clojure has in JavaScript which doesn't exactly encourage immutability at the language level.

Do you mean internal algorithms? Clojure's persistent sorted map is built on a persistent version of a red-black tree, which has many similarities to a mutable red-black tree, so in this case the internal algorithms are very similar. Clojure persistent hash map, however, has a very different structure internally compared to most mutable hash tables, and likewise very different internal algorithms.

On the other hand, the performance provided by Clojure's persistent collections are close to what you'd expect of their mutable cousins, so the algorithms and situations in which one would use Clojure's hash or sorted maps are likely very similar to where you'd use mutable versions in an imperative program.