Implement `fold` on a "Rose Tree"

Question

Given the following algebraic data type, a Rose Tree:

data Tree a = Node {
 rootLabel :: a,
 subForest :: [Tree a]
} 

I attempted a foldTree function to fold over this list: (credit to this class's homework from 2013:

treeFold :: (b -> [b] -> b) -> (a -> b) -> Tree a -> b
treeFold f g tree = f (g (rootLabel tree)) (map (g . rootLabel) (subForest tree))

test

*Party> let tree = Node { rootLabel = 100, subForest = [] }
*Party> let tree2 = Node { rootLabel = 200, subForest = [tree] }
*Party> add tree2
300

Please review this implementation.

Given my definition of treeFold, I don't see how I could fold over a Tree Char, producing a [Char]/String result.

My understanding is that, for the return type, b, it can't be [a].

Answer 1

The implementation isn't correct, because it doesn't traverse sub-trees. Consider

Node 1 [Node 2 [Node 3 []]]

Then your folding function will only fold over 1 and 2, but not over 3.

If you have a recursive structure like this, a folding function over it must also be recursive. Otherwise it won't be able to traverse arbitrarily large recursive structure.

For the other question: If you specialize the folding function as

treeFold :: ([Char] -> [[Char]] -> [Char]) -> (Char -> [Char])
 -> Tree Char -> [Char]

by setting b = [Char], you get what you're looking for - converting a Tree Char to String. You just need to supply the two function for folding, for example

treeFold (\x ys -> x ++ concat ys) (: [])

---

Update: The signature also isn't correct. The general rule is that the folding function should have one additional argument for each constructor of the data type where recursive types (here Tree a) are replaced by the result of the fold:

treeFold :: (a -> [b] -> b) -> Tree a -> b

For example for a list you have 2 constructors: (:) :: a -> [a] -> [a] and [] :: [a], so its folding function is

foldr :: (a -> b -> b) -> b -> [a] -> b

• Kevin Meredith: Thank you, Petr. Does my function signature look right?
• Petr: @KevinMeredith Updated.
• Kevin Meredith: Why isn't the correct signature's first argument: (a -> [b] -> b)?
• Petr: @KevinMeredith You're absolutely right, I mixed up a and b. Of course, it must be the type of the result. Fixed.