A recursive data structure is a type whose definition contains itself. That self-reference lets one type describe values of unbounded depth: a list can hold an element and the rest of the list, while a terminal case marks the end. In functional design, such types help make the shape of a domain explicit. section 2.1.2
A list that contains more of itself
The definition `data List a = Cons a (List a) | Nil` has two alternatives. `Nil` ends a list; `Cons` stores one `a` and a further `List a`. Thus `Cons johnDoe (Cons janeDoe Nil)` represents two people without requiring a separate list type for each possible length. section 2.1.2
A useful way to read a recursive definition is to identify its parts:
- A base case creates the smallest valid value, such as `Nil`. section 2.1.2
- A recursive case adds one layer while referring back to the same type, such as `Cons a (List a)`. section 2.1.2
- Operations follow the same shape: handle the base case, then process one layer and recur on the remainder. section 2.1.2
Recursive structure is not limited to collections. `Free t a` is recursive because its `Free` constructor contains `t (Free t a)`. That wrapping keeps a chain of actions under one type, `Free SandwichConstructor a`, regardless of how many actions the chain contains. section 6.3.4
Without the recursive wrapper, repeatedly nesting `SandwichConstructor` makes each longer script acquire a different, increasingly nested type. The recursive `Free` structure avoids that uncontrolled signature growth while preserving the chain of actions. section 6.3.4
Recursing over structure with fmap
The `Functor List` implementation maps `Nil` to `Nil`. For `Cons a l`, it applies a function to `a` and recursively maps the remaining list `l`; mapping `age` over people therefore produces a list of ages with the same shape. section 2.1.2
data Free t a = Pure a | Free (t (Free t a)) type SandwichRecipe a = Free SandwichConstructor a
Inspect the two constructors of `Free`: `Pure` provides a stopping case, and `Free` embeds another layer of the same recursive type inside an action constructor. section 6.3.4
