Haskell Design Patterns

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 ...