If you can't change a variable's value in Haskell, how do you create data structures?

Question

As per the title.

I have the following code which creates a binary search tree, but if I want it created and changed dynamically with user input, how would I do that if I can't change the value of a variable in haskell?!?

find :: (Ord a) => Node a -> a -> Bool
find (Node val left right) s
    | s == val  = True
    | s < val  = find left s
    | s > val  = find right s

find Empty s = False

data Node a = Node a (Node a) (Node a)
              | Empty

myTree = Node "m"   (Node "a" Empty Empty)
        (Node "z" Empty Empty)

Thanks in advance!

Answer 1

The idea behind purely functional data structures is to compute new values instead of changing them and to pass them (recursively) in parameters instead of storing them globally.

So given a function

insert :: Ord a => Node a -> a -> Node a

your programm could look like this

-- Let the user enter k values that are stored in a tree structure
addTreeItems :: Int -> Node Int -> IO (Node Int)
addTreeItems 0 tree = return tree
addTreeItems k tree = do
    putStr "Enter new item: "
    item <- readLn
    addTreeItems (k - 1) (insert tree item) -- Recursively pass the tree

main = do
    tree <- addTreeItems 10 Empty
    -- ...

Using monadic helper functions, this could be simplified to things like

(foldl insert Empty) `liftM` (sequence $ replicate k (putStr "Enter new item: " >> readLn))

If you want to update values at a certain position, you'll need more advanced datastructures like a zipper, that are nevertheless still purely functional!

Answer 2

Dario gave a good direct answer. If you want more in-depth information, there's Purely Functional Data Structures by Chris Okasaki, an entire book on the subject. I bought it myself, but sadly, I don't have the time to experiment with the ideas.

Answer 3

You allocate a new tree node and the old one sticks around. This technique requires a really good allocator, but it enables all sorts of nifty devices because other parts of the program still have access to old nodes. This is a godsend for certain kinds of speculative algorithms or other tricks involving so-called "persistent data structures".

Eventually you allocate a new root for your tree and what then? As Dario says, you pass it as a parameter to a function (instead of storing it in a global variable).

So

• Mutation of a field in a struct allocated on the heap becomes allocation of a new struct on the heap.

• Mutation of a global variable becomes passing a parameter to a function

Sometimes it also makes sense to take what would have been a collection of global variables in C and put them all in an object allocated on heap.

---

P.S. If you really want to, you can have mutable global variables in Haskell. It is, after all, the world's finest imperative programming language (according to Wadler or Peyton Jones, I forget whom). But if you are asking this question, you really don't want to. Yet.