Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 2 / a / Solution 2026-10-31
View more
A tree fold first folds every child rose tree, then supplies the resulting list and the current label to the combining function:
foldRTree :: (a -> [b] -> b) -> RTree a -> b
foldRTree f (Node x children) =
  f x (map (foldRTree f) children)
The label type a and result type b are independent, so the polymorphic type needs no class constraint. With f x ys = x + sum ys, every label is counted exactly once; the illustrated labels sum to 28.
The printed source gives the signature exampleRTree but binds exampleRTRee, with different capitalization. They are different Haskell names; the demonstration requires using one spelling consistently. This typo does not affect the tree fold definition.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 4 / a / Solution 2026-10-31
View more
The most general polymorphic type is
unfold :: (s -> Bool) -> (s -> a) -> (s -> s) -> s -> [a]
The stopping predicate consumes a state, the output function turns that state into one list element, and the transition function supplies another state of the same type. The state type and output type need not coincide. This is a list unfold with separate stopping, output and transition arguments.
Read the full article