CODEWITHSUNDEEP
data-structureshaskellimmutability
user500944
user500944

Reputation:

Complex data structures in Haskell - how do they work?

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?

Upvotes: 17

Views: 5344

Answers (2)

ScottWest
ScottWest

Reputation: 1936

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.

Upvotes: 27

Lee
Lee

Reputation: 144206

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

Upvotes: 33

Related Questions