Reputation: 1
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
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
Reputation: 49238
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