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

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 开发者_Go百科"a" Empty Empty)
                    (Node "z" Empty Empty)

Thanks in advance!

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!

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.

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.