CODEWITHSUNDEEP
haskelltreeroot
user1118043
user1118043

Reputation: 1

Haskell: Get path from every leaf node to root

I have a simular qwestion Haskell: Get path from every leaf node to root in a Bin tree structure. And there no answer.

(Find way). coords (2, 2) -> [2, 1, 0] I have tree where every level start with 0.

   0
  / \
 0   1
/ \ / \
0 1 2 3
........

I wrote some code, but it doesn't work (of cource...)

fromroot 0 _ _ = []
fromroot i j (Node t1 x t2)
   = if (j div (2^(i-1)))
        then x++ (fromroot (i-1) (j-2^(i-1)) t2)
        else x++ (fromroot (i-1) j t1)

tree i took from there thread.

data Tree a = Node (Tree a) a (Tree a)

myBuild :: Int  -> Tree Int
myBuild n = (Node (myBuild (n*2)) n (myBuild (n*2+1)))

Hope, you'll help me.

UPD 1

Input > fromroot 3 2 (myBuild 0) and error on myBuild function.

    Couldn't match expected type `[a0]' with actual type `Int'
    Expected type: Tree [a0]
      Actual type: Tree Int
    In the return type of a call of `myBuild'
    In the third argument of `fromroot', namely `(myBuild 0)'
Failed, modules loaded: none.

Upvotes: 0

Views: 1108

Answers (2)

dave4420
dave4420

Reputation: 47072

You think you have written fromroot to take a Tree a as its third argument, but instead you have written it to take a Tree [a].

This is because you use x as a list, instead of prepending it to the list returned from the recursive call.

To prepend a single element to a list, you use :. ++ is for concatenating two lists together.

(I also think your if condition should be 0 /= (j `div` (2^(i-1))) instead of j div (2^(i-1)), because (1) to use named functions as an operator they must be enclosed in backticks, and (2) if takes a Bool, and does not cast from e.g. Int for you. But that wasn't what the error message you posted was complaining about.)

There may be other mistakes; I haven't checked.

Upvotes: 0

Dario
Dario

Reputation: 49238

Hint

Let's try to get element (2,3) [Level 2, Element #3 as an explanation for the coordinates used here] out of your original tree.

   0
  / \
 0   1
/ \ / \
0 1 2 3

Now this is the same as getting element (1,1) out of the subtree (which is trivial to do!)

 1
/ \
2 3

Now think of an example for a tree with one more level. And do the recursion trick.

Upvotes: 1

Related Questions