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!
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With