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. 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.

Ancestors (11)

  1. 2
  2. Functional programming, design and analysis of algorithms
  3. 2016
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version