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 / f / Solution

The head of each recursively obtained list is the original child. Hence the tree fold has retained enough information to reconstruct the parent:

subs :: Tree a -> [Tree a]
subs = fold (\x -> [One x]) combine
  where
    combine ls rs = Two (head ls) (head rs) : (ls ++ rs)

The invariant is that every folded result is nonempty and begins with the subtree being folded. It holds at One; the displayed combining operation preserves it at Two. Thus neither use of head encounters an empty list, and the remaining entries agree with the recursive preorder traversal.