= 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>.
Back to article page
