I want to implement flattenning a tree using my foldTree function that I defined and in-order traversal.Which should return a list after flattening.
data Tree t = Leaf t
| Tree (Tree t) t (Tree t)
foldTree :: (t1 -> t -> t1 -> t1) -> (t -> t1) -> Tree t -> t1
foldTree treeFn leafFn tree =
case tree of
Leaf v -> leafFn v
Tree leftTree q rightTree -> treeFn (foldTree treeFn leafFn leftTree) q (foldTree treeFn leafFn rightTree)
Input : foldTree (\t1 t t2->t1 + 5*t + t2) (\x->x+9) (Leaf 5)
Expected Output : 14
Input : foldTree (\t1 t t2->t1 + 3*t + t2) (\x->x+5) (Tree (Leaf 3) 2 (Leaf 4))
Expected Output : 23
I tried the following code but it uses recursion.I want to call foldTree from flattenTree to implement the flattening of tree instead of making a recursive call to flatTree.(Using foldTree functions in flattenTree).Can anyone help me on how to integrate it.
flatTree :: Tree a -> [a]
flatTree tree =
case tree of
Leaf v -> [v]
Tree p v r -> (flatTree p) ++ [v] ++ (flatTree r)
Input: flatTree (Tree (Leaf 5) 3 (Tree (Leaf 3) 2 (Leaf 4)))
Expected output : [5,3,3,2,4]
Look at the type of foldTree.
foldTree :: (b -> a -> b -> b) -> (a -> b) -> Tree a -> b
You can see that b is the result type of the catamorphism. foldTree works by folding each sub-tree to obtain a result b for each, then combining them using the folding function.
Since you want the result to be a flattened list of the tree's elements, let's set b ~ [a].
foldTree :: ([a] -> a -> [a] -> [a]) -> (a -> [a]) -> Tree a -> [a]
So the second argument of foldTree should be something which injects a single element a into a list [a], and the first should be one that combines two lists with an element to make a bigger list.
flatTree = foldTree (\xs x ys -> xs ++ x : ys) (\x -> [x])
Incidentally, GHC is able to write your flatTree function for you, just by looking at the structure of the type. flatTree :: Tree a -> [a] matches the type of toList :: Foldable f => f a -> [a], which is part of the Foldable class. All you need to do is say the magic words, deriving Foldable, and GHC will spit out an instance of Foldable.
{-# LANGUAGE DeriveFoldable #-}
data Tree t = Leaf t
| Tree (Tree t) t (Tree t)
deriving Foldable
flatTree :: Tree a -> [a]
flatTree = toList
Because of the way the Tree constructor is laid out, toList will perform an in-order traversal. This can be varied by adjusting the definition of the Tree constructor.