listTree' :: Tree a -> [a]
listTree' t = foldTree f z t []
where
f = undefined
z [] = []
Need help solving for f. when I insert f a b c = a [b] c
I get an error
data Tree a
= Tip
| Bin (Tree a) a (Tree a)
deriving (Show, Eq)
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree f z Tip = z
foldTree f z (Bin l x r) = f (foldTree f z l) x (foldTree f z r)
here is foldTree and data type for tree
CodePudding user response:
In order to achieve linear time, you should let foldTree f z t
return a function that takes a list and returns a list.
This means that for z
, a leaf, we simply return the given list, and we thus do not prepend any value. For f
we will take the list, call it with the right subtree, then prepend that list with the value of that Bin
node, and finally call it with the left subtree, so:
listTree' :: Tree a -> [a]
listTree' t = foldTree f id t []
where f x y z ls = x (y: z ls)
Here ls
is thus the list we need to process, z
is a function to prepend the items of the right subtree to ls
, y
is the value stored in that node, and x
is a function that prepends the items of the left subtree to the list.
We can define f
, as @chi says as f x y z = x . (y:) . z
. We thus first apply the function generated for the right subtree, then prepend the list with y
, and then run it through the function of the left subtree.