What is the benefit of purely functional data structure?

Question

There are large number of texts on data structures, and libraries of data structures code. I understand that purely functional data structure is easier to reason about. However I have trouble to understand the real world advantage of using purely functional data structure in pragmatic code (using functional programming language or not) over the imperative counterpart. Can somebody provide some real world cases where purely functional data structure has advantage and why?

Examples along the line like I use data_structure_name in programming_language to do application because it can do certain_thing.

Thanks.

PS: What I mean by purely functional data structure is not the same as persistent data structure. Persistent data structure is a data structure that doesn't change?? On other hand purely functional data structure is a data structure that operates purely.

Take note that a singly linked lists as implemented by F# is a purely functional data structures: http://en.wikipedia.org/wiki/Purely_functional — ChaosPandion, Dec 09 '10 at 15:48
What do you mean by "purely" such that it differs from immutable? — Marcelo Cantos, Dec 09 '10 at 16:34
Immutability is a characteristic of purely functional data structures. period. I don't believe they are 'easier to reason about', but USING them is easier to reason about. — nlucaroni, Dec 09 '10 at 18:37
This statement: “purely functional data structure is a data structure that operates purely” it's circular. If you'd described it as a “data structure that functionally operates purely” you'd have had a purely circular definition. :-) — Donal Fellows, Dec 09 '10 at 19:45

score 75 · Accepted Answer · answered Dec 09 '10 at 16:11

75

Purely functional (aka persistent or immutable) data structures give you several advantages:

you never have to lock them, which extremely improves concurrency.
they can share structure, which reduces memory usage. For example, consider list [1, 2, 3, 4] in Haskell and some imperative language like Java. To produce new list in Haskell you only have to create new cons (pair of value and reference-to-next-element) and connect it to the previous list. In Java you have to create completely new list not to damage the previous one.
you can make persistent data structures lazy.
also, if you use functional style, you can avoid thinking of time and sequence of operations, and so, make your programs more declarative.
fact, that the data structure is immutable, allows you to make some more assumptions and so expand capabilities of language. For example, Clojure uses the fact of immutability to correctly provide implementations of hashCode() method on each object, so any object may be used as a key in a map.
with immutable data and functional style you can also freely use memoization.

There's much more advantages, in general, it is another way of modeling the real world. This and some other chapters from SICP will give you more accurate view of programming with immutable structures, its advantages and disadvantages.

answered Dec 09 '10 at 16:11

ffriend

27,562
13
91
132

9

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 would also (obviously) be a good reading on this topic. – rks Dec 09 '10 at 16:16
4

@rks: And see [What's new in purely functional data structures since Okasaki?](http://cstheory.stackexchange.com/q/1539/634) for complements to this great, but now a little dated, book. – Gilles 'SO- stop being evil' Dec 09 '10 at 19:49
Laziness does not use side-effects in its implementation? How does that work? And if it does, does it remain true that you never have to lock purely functional lazy data structures? – Pascal Cuoq Dec 09 '10 at 21:50
Laziness does use side-effects in its implementation. However, in a pure language, that doesn't mean you need locking. If two threads happen to evaluate the same expression at the same time, they might duplicate work, but that's it. It's impossible to distinguish between the results of the two evaluations in a pure context. – Carl Dec 09 '10 at 22:36
2

@Carl I find you extremely optimistic regarding the effects of lock-free concurrent accesses to shared memory. I am sure I could distinguish between a coherent (evaluated or unevaluated) expression on the one hand and shared memory transitioning without locking from one to the other on the other hand. – Pascal Cuoq Dec 09 '10 at 22:46
1

If you think that lock-free shared memory "just work", take a look at http://www.cl.cam.ac.uk/~pes20/weakmemory/ – Pascal Cuoq Dec 09 '10 at 22:48
@Pascal Cuoq: Lazy data structures use some kind of generators, i.e. they generate next value on demand. Simple example: lazy list of integers is a cons (pair of elements), where car (first element of pair) is, let's say, `1` and the cdr (second element of pair) is delayed object, which when called produces new cons with car `2` and cdr, again, new delayed object. Everything is described in terms of 2 procedures/macros/special forms - `future` and `delay`. More on them [here](http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5). – ffriend Dec 09 '10 at 22:56
@ffriend `(begin (set! result (proc)) (set! already-run? true) ...` from that link does not seem compatible with lock-free concurrent access. – Pascal Cuoq Dec 09 '10 at 23:03
@Pascal Cuoq: 1. it's about memoization, not about laziness itself. 2. In the worst case `(proc)` will be evaluated twice, but since it has no side effects (_must not_ have side effects by rules of using lazy data structures), the result will be the same. 3. Even if implementation of such list must use synchronization for some reason, [STM](http://en.wikipedia.org/wiki/Software_transactional_memory) is good solution, but not locks. Each lock refreshes line of processor cache, so it costs a lot. – ffriend Dec 09 '10 at 23:24
2

@Pascal Cuoq: GHC exists. Go ahead and find an incoherency issue in concurrent evaluation of a thunk. I'm sure Simon Marlow would be concerned if you found a real bug. But I just don't see it happening. There have been many very careful choices made in runtime representations to ensure coherency so long as your actions are pure. (If you do something inside the thunk in terms of unsafePerformIO, all bets are off.) – Carl Dec 09 '10 at 23:44
1

The statements about concurrency and locking here (except Pascal's) are complete bullshit. You don't have to lock purely functional data structures because **they don't even support concurrent writes** but you actually get **more contention** because every thunk introduces a side-effect when it is first forced. – J D Dec 25 '10 at 12:15
1

harrop is confusing laziness with lack of mutation. you can have data structures which are purely functional and thunk-free as well. and you can have lock-free strategies for updating thunks for that matter. – sclv Dec 25 '10 at 23:06
"harrop is confusing laziness with lack of mutation. you can have data structures which are purely functional and thunk-free as well". Which is precisely why I wrote "lazy thunks (if any)" in my answer. "you can have lock-free strategies for updating thunks for that matter" but you still get more contention, just as I said. – J D Dec 27 '10 at 15:24
1

I'd like to know what the word "contention" means in the absence of locks or synchronization. – sclv Dec 27 '10 at 17:09
1

Locks and synchronization in user code are just some of the more visible forms of contention. Others include contention for "hidden" shared resources like the garbage collector or shared caches. – J D Dec 27 '10 at 18:52
Just for clarification of my understanding, your second bullet regarding the reduced memory usage is illustrated by @NikiYoshiuchi answer's diagram, correct? – Honinbo Shusaku Sep 26 '16 at 15:22
@Abdul: yes, exactly. – ffriend Sep 26 '16 at 21:06

score 25 · Answer 2 · answered Dec 09 '10 at 16:18

In addition to shared memory safety most purely function data structures also give you persistence, and practically for free. For example, let's say I have a set in OCaml, and I want to add some new values to it I can do this:

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

a remains unmodified after adding the new characters (it only contains a-d), while b contains a-h, and they share some of the same memory (with a set it's kind of tricky to tell how much memory is shared since it's an AVL tree and the shape of the tree changes). I can continue doing this, keeping track of all the changes I've made to the tree allowing me to go back to a previous state.

Here's a great diagram from the Wikipedia article on Purely Functional that shows the results of insert the character 'e' into the binary tree xs:

alt text

score 14 · Answer 3 · answered Dec 09 '10 at 15:30

14

Erlang programs use purely functional data structures almost exclusively, and they reap substantial benefits by scaling almost seamlessly to multiple cores. Because shared data (mainly binaries and bit strings) is never modified, there is never a need to lock such data.

answered Dec 09 '10 at 15:30

Marcelo Cantos

181,030
38
327
365

3

Erlang scales from poor absolute performance on one core to poor absolute performance on `n` cores. – J D Dec 25 '10 at 12:19
3

@Jon: Firstly, your comment is a sweeping generalisation; Erlang performs very well in messaging applications, where the predominant workload is communication. Secondly, your comment misses the point. Yes, Erlang is a slow language, but it still benefits from using immutable data types. – Marcelo Cantos Dec 25 '10 at 22:53
1

"Erlang performs very well in messaging applications, where the predominant workload is communication". Not if your communication is between multiple cores on the same CPU, as your answer implies. This is the difference between parallel and concurrent programming. Erlang is great for concurrency but bad for parallelism. Multicore is irrelevant here: Erlangers just name drop it because it is a hot topic right now. If multicore benefits an Erlang program significantly then Erlang was the wrong tool for the job. – J D Dec 27 '10 at 00:06

score 11 · Answer 4 · answered Dec 25 '10 at 22:45

Purely functional data structures have the following advantages:

Persistence: old versions can be reused safe in the knowledge that they cannot have been changed.
Sharing: many versions of a data structure can be kept simultaneously with only modest memory requirements.
Thread safety: any mutation is hidden inside the lazy thunks (if any) and, therefore, handled by the language implementation.
Simplicity: not having to keep track of state changes makes purely functional data structures simpler to use, particularly in the context of concurrency.
Incrementality: purely functional data structures are composed of many tiny parts, making them ideal for incremental garbage collection leading to lower latencies.

Note that I have not listed parallelism as an advantage of purely functional data structures because I do not believe this to be the case. Efficient multicore parallelism requires predictable locality in order to leverage caches and avoid getting bottlenecked on shared access to main memory and purely functional data structures have, at best, unknown characteristics in this regard. Consequently, many programs that use purely functional data structures do not scale well when parallelized on a multicore because they spend all of their time in cache misses, contending for shared memory pathways.

What I mean by purely functional data structure is not the same as persistent data structure.

There is some confusion here. In the context of purely functional data structures, persistence is a term used to refer to the ability to refer back to previous versions of a data structure safe in the knowledge that they are still valid. This is a natural result of being purely functional and, therefore, persistence is an inherent characteristic of all purely functional data structures.

Also, on the topic of parallelism, immutability (if it were not for thunks) gives you *data parallelism* for free (modulo the bad cache behavior you mention), however can you take advantage of multicore hardware to perform *task parallelism*? As inter-thread communication necessarily involves mutation of a shared state, it looks to me that you need special support for this, as for IO, but then you break purity even more. I guess this is what `MVar` and the STM library of Concurrent Haskell do? — Maëlan, Mar 27 '21 at 12:05
If your thread starts with one values, sends and receives no values and returns with one value then it is effectively a function and easily made pure but, yes, in the general case it isn't pure. But the real killer is that even a "pure" thread can cause impure problems like false sharing that destroy performance. I'd say MVar and STM are more for concurrency than parallelism. — J D, Apr 16 '21 at 08:57

score 9 · Answer 5 · answered Dec 09 '10 at 15:37

Take this little snippet of F#:

let numbers = [1; 2; 3; 4; 5]

You can say with 100% certainty that that is a immutable list of integers 1 through 5. You can pass around a reference to that list and never have to worry that the list may have been modified. That is enough reason for me to use it.

What is the benefit of purely functional data structure?

5 Answers5

Linked