= Solution
Use `concat [] = []`, `concat (ys:yss) = ys ++ concat yss`, the corresponding equations for `map`, <associativity> of <list concatenation>, and `(r:ys) ++ zs = r:(ys ++ zs)`. For an empty forest,
``
flatten2 [] xs
= concat (map flatten []) ++ xs
= [] ++ xs
= xs
``
For a nonempty forest, write its first <rose tree> as `Node r children`:
``
flatten2 (Node r children : trees) xs
= (flatten (Node r children) ++ concat (map flatten trees)) ++ xs
= (r : concat (map flatten children))
++ (concat (map flatten trees) ++ xs)
= r : (concat (map flatten children) ++ flatten2 trees xs)
= r : flatten2 children (flatten2 trees xs)
``
Thus the recursive <Haskell> definition is
``
flatten2 :: [RTree a] -> [a] -> [a]
flatten2 [] xs = xs
flatten2 (Node r children : trees) xs =
r : flatten2 children (flatten2 trees xs)
``
The nested call supplies the continuation of the <preorder traversal> as a suffix. \b[Each label is emitted once], without repeated <list concatenation> of an already flattened subtree. For a finite forest, constructing its entire contribution takes linear time in its number of <vertices>, without traversing the supplied suffix `xs`.
Back to article page
