Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 1 / c

The natural tree fold replaces each data constructor by the supplied operation:

fold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
fold one two (One x)   = one x
fold one two (Two l r) = two (fold one two l) (fold one two r)

Its reconstruction identity is fold One Two = id. More generally a function h equals fold one two on finite trees exactly when h (One x) = one x and h (Two l r) = two (h l) (h r). These equations determine the result by structural induction, expressing why this is the natural structural recursion for this datatype.