Origami programming

	"Recursive equations are the 'assembly language' of functional programming, and direct recursion the go-to"
	--Jeremy Gibbons, Origami Programming (The Fun of Programming), 2003

In the previous section, we wrote a generic function for the recursive types Tree and List. In this section, we look at origami programming, a style of generic programming that focuses on the core patterns of recursion: map, fold, and unfold.

Tying the recursive knot

There is a primal type that underlies recursive datatypes, known as Fix:

  data List' a = Nil'   | Cons' a (List' a)
  data Tree  a = Leaf a | Node  a (Tree a) (Tree a)

  data Fix s a = FixT {getFix :: s a (Fix s a)}

The parameter s represents the shape, while a refers to an instance of the type. The Fix datatype is named after the fixed point of a function, which is defined by:

  f (fix f) = fix f

To express Tree and List in terms of Fix, we need to rewrite them using implicit recursion:

  data List_ a r = Nil_    | Cons_ a r
    deriving...