= Solution
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 \b[`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.
Back to article page
