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