A tree fold replaces each constructor by its interpretation:
foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
  combine (foldTree combine zero left)
          equal
          (foldTree combine zero right)

fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []
Induction on the finite tree shows equality with fromTree: the empty tree produces the empty output, and the combining function concatenates the two correctly flattened children around the node's bucket. The result type is independent of the key type; other choices can compute a size or another summary using the same structural recursion.

Ancestors (12)

  1. e
  2. 2
  3. Functional programming, design and analysis of algorithms (resit)
  4. 2021
  5. Past exam of the year 1 of the computer science course of the University of Oxford
  6. Year 1 of the computer science course of the University of Oxford
  7. Computer science course of the University of Oxford
  8. Undergraduate course of the University of Oxford
  9. Course of the University of Oxford
  10. University of Oxford
  11. List of universities
  12. 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