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

Get Haskell Design Patterns now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.