CODEWITHSUNDEEP
haskellfunctional-programming
Lunar
Lunar

Reputation: 4711

Haskell add value to tree

Im trying to make a funciton which allows me to add a new value to a tree IF the value at the given path is equal to ND (no data), this was my first attempt.

It checks the value etc, but the problem, is i want to be able to print the modified tree with the new data. can any one give me any pointers? I have also tried making a second function that checks the path to see if its ok to add data, but im just lost to how to print out the modified tree?

Upvotes: 0

Views: 899

Answers (3)

jberryman
jberryman

Reputation: 16645

As iuliux points out, your problem is that you are treating your BTree as though it were a mutable structure. Remember functions in haskell take arguments and return a value. That is all. So when you "map over" a list, or traverse a tree your function needs to return a new tree.

The code you have is traversing the recursive tree and only returning the last leaf. Imagine for now that the leaf at the end of the path will always be ND. This is what you want:

add :: a -> Path -> Btree a -> Btree a
add da xs ND = Data da
add _  [] _  = error "You should make sure this doesn't happen or handle it"
add da (x:xs) (Branch st st2) = 
               case x of 
                    L -> Branch (add da xs st) st2
                    R -> Branch st (add da xs st2)

Notice how in your original code you discard the Branch you pattern match against, when what you need to do is return it "behind you" as it were.

Now, on to the issue of handling situations where the leaf you arrive it is not a ND constructor:

This type of problem is common in functional programming. How can you return your recursive data structure "as you go" when the final result depends on a leaf far down the tree?

One solution for the trickiest of cases is the Zipper, which is a data structure that lets you go up down and sideways as you please. For your case that would be overkill.

I would suggest you change your function to the following:

add :: a -> Path -> Btree a -> Maybe (Btree a)

which means at each level you must return a Maybe (Btree a). Then use the Functor instance of Maybe in your recursive calls. Notice:

fmap (+1) (Just 2) == Just 3
fmap (+1) (Nothing) == Nothing

You should try to puzzle out the implementation for yourself!

Upvotes: 5

dbyrne
dbyrne

Reputation: 61011

We really need to see the Path and Error data types to answer your question, but you can print out your trees using the IO Monad:

main :: IO()
main = do let b = Branch ND (Branch (Data 1) (Data 2))
          let b1 = add 10 [L] b --actual call depends on definition of Path
          (putStrLn . show) b1

Upvotes: 1

Iulius Curt
Iulius Curt

Reputation: 5114

I'm no expert in Haskell, but functional programming only works with functions. So kind of anything is a function.
Now, your function takes some input and returns something, not modifing the input. You have to retain the returned tree somewhere and that will be your new tree, the one with inserted element in it

Upvotes: 3

Related Questions