Complex data structures in Haskell - how do they work?

16
votes

As I figured out, variables in Haskell are immutable (thus, they are not really `variables').

In this case, if we have a complex and big data structure, like a red-black tree, how are we supposed to implement operations that actually change the data structure?

Create a copy of the tree each time an element is inserted or deleted?

2
data-structureshaskellimmutability
"Thus, they are not really `variables'" — Sure they are. For instance, when a mathematician says "Let G be the group (S,*), where ...", the G is a variable, even though it's never going to change. It's the same principle in Haskell. – Antal Spector-Zabusky
you certainly raise an interesting point, indeed the structure change a bit to accommodate immutability without sacrificing performance. Think of your structure as an oriented graph (where an edge from A to B means that A holds a reference / index to B), then if you wish to change B, any vertex from which B was accessible need be copied and its reference updated. I still have not found how to represent a Skip List in Haskell for example :) – Matthieu M.

2 Answers

33
votes

Yes, the solution is to return a new data structure which represents the modified value, however there is no requirement to copy the entire structure for your example (red-black trees) since you can just copy the nodes on the path from the root to the inserted node. This allows the insert operation to be the same complexity as the imperative version.

Chris Okasaki's Purely functional data structures contains a number of implementations of immutable data structures - this book is a modified version of his phD thesis which you can find here

27
votes

Your intuition about copying is exactly the right direction you should be thinking. However, the 'copying' intelligently implemented by the Haskell runtime. For example, given

data Tree = Empty | Branch Tree Integer Tree

You could implement a function to replace the left branch:

replaceLeft :: Tree -> Tree -> Tree
replaceLeft (Branch _ i r) newLeft = Branch newLeft i r

The result isn't that you create a entire copy of the new tree, as that isn't necessary. The value i and the trees r and newLeft are unchanged so we don't have to copy their contents into fresh memory.

The new Branch that is created (this is the only real allocation in this example: the creation of the structure to hold the left/right trees on the Integer) still references the exact same values from the old branch, no copying needed!

Since the data structures are immutable, there's no harm in doing this.