How to define listTree so that it runs in linear time?

November 5, 2021

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

>Solution :

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.