Haskell: Get path from every leaf node to root

0
votes

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.
2
haskelltreeroot
Do you build the thee along the way, or you have a ready-made tree to traverse? – 9000
along the way. But it doesn't matter – user1118043
What do you expect j div (2^(i-1)) to do? – dave4420
Btw, it helps us if you post the compiler error message (when the code doesn't compile) or a failing test case (i.e. sample input, the output you expect/desire from your function for that input, the output your function actually gives you). – dave4420
j div (2^(i-1)) should choose go to left or right. I upd 1st message. – user1118043

2 Answers

1
votes

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.

0
votes

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.