"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 (Show) data Tree_ a r = Leaf_ a | Node_ a r r deriving (Show)
Here, we replaced the explicit recursive reference with a more vague type parameter r
. This allows us to express ListF
and TreeF
in terms of Fix
:
type ListF a = Fix List_ a type TreeF a = Fix Tree_ a
The List_
and Tree_
types don't explicitly recur, so Fix
ties the recursive knot around the shape (refer to Datatype-Generic Programming by Gibbons). We can construct a List_
instance in a similar way:
aList1 = Cons_ 12 Nil_ -- aList :: List_ Integer (List_ a r) aList2 = Cons_ 12 (Cons_ 13 Nil_) -- aList2 :: List_ Integer (List_ Integer (List_ a r))
Although the type signatures show that this is quite different from regular lists, to construct the ListF
lists, we need to wrap the FixT
constructor around each nesting:
aListF :: ListF Integer -- Fix List_ Integer aListF = FixT (Cons_ 12 (FixT (Cons_ 13 (FixT Nil_))))
We deconstructed List
and Tree
into the generic recursion type Fix
. This means we can write generic functions against the Fix
type.
To find our way toward a generic map
, let's write a map function for the recursive type ListF
:
mapL f listF = case list_ of (Cons_ x r) -> FixT $ Cons_ (f x) (mapL f r) Nil_ -> FixT Nil_ where list_ = getFix listF showListF :: (Show a) => ListF a -> String showListF (FixT (Cons_ x r)) = (show x) ++ ", " ++ (showListF r) showListF (FixT (Nil_) = "Nil_" main = putStrLn . showListF $ mapL (*2) aListF
This is clumsy because in both clauses of the case statement we have to unwrap the list (with getFix
) and then wrap the result again (with FixT
). The BiFunctor
typeclass gives us what we need to clarify our mapL
function:
"It turns out that the class Bifunctor provides sufficient flexibility to capture a wide variety of recursion patterns as datatype-generic programs." | ||
--Gibbons, DatatypeGeneric Programming |
The Bifunctor
type-class is just a Functor
that can have two functions applied to it instead of one (which is already defined in Data.Bifunctor
):
class Bifunctor s where bimap :: (a -> c) -> (b -> d) -> (s a b -> s c d)
Let's make List_
and Tree_
types instances of the BiFunctor
type-class:
instance Bifunctor List_ where bimap f g Nil_ = Nil_ bimap f g (Cons_ x r) = Cons_ (f x) (g r) instance Bifunctor Tree_ where bimap f g (Leaf_ x) = Leaf_ (f x) bimap f g (Node_ x rl rr) = Node_ (f x) (g rl) (g rr)
Now, we can write a generic map:
gmap :: Bifunctor s => (a -> b) -> Fix s a -> Fix s b gmap f = FixT . bimap f (gmap f) . getFix main = putStrLn . showListF $ gmap (*2) aListF
We can also use the bimap
function to implement a generic fold function
:
gfold :: Bifunctor s => (s a b -> b) -> Fix s a -> b
gfold f = f . bimap id (gfold f) . getFix
Again, we unwrap the list with getFix
, but this time, instead of rewrapping, we apply f
. In other words, gfold
replaces all occurrences of FixT
with f
:
-- FixT (Cons_ 12 (FixT (Cons_ 13 (FixT Nil_)))) -- f (Cons_ 12 (f (Cons_ 13 (f Nil_))))
To fold together a sum, we create an adder:
addL (Cons_ x r) = x + r
addL Nil_ = 0
main = print $ gfold addL aListF
Where fold
is a consumer of data structures, unfold
is a producer that unfolds a structure from a single value. To unfold a regular list, we need a value and some functions:
unfoldL stopF nextF val = if stopF val -- stop if True then [] else val : (unfoldL stopF nextF (nextF val)) main = print $ unfoldL (< (-10)) (x -> x - 1) 10
We can use the bimap
function to create a generic unfold:
gunfold :: Bifunctor s => (b -> s a b) -> b -> Fix s a
gunfold f = FixT . bimap id (gunfold f) . f
For example, we can use gunfold
to generate a list of values from a single value:
toList 0 = Nil_
toList n = (Cons_ n (n-1))
main = putStrLn . showListF $ gunfold toList 10
-- 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, Nil_
Composing unfold with fold makes sense because by doing so, we are connecting a producer with a consumer:
main = print $ gfold addL (gunfold toList 100)
(Refer to Gibbons' Origami programming and Datatype-generic programming, where you will find this pattern under hylomorphisms.)
The unfold
and fold
functions are each other's mirror images:
gunfold f = FixT . bimap id (gunfold f) . f gfold f = f . bimap id (gfold f) . getFix
The hylo
function is their composition:
hylo f g = g . bimap id (hylo f g) . f main = print $ hylo toList addL 100
"The beauty of all of these patterns of computation is the direct relationship between their shape and that of the data they manipulate" "The term origami programming for this approach because of its dependence on folds and unfolds" | ||
--Gibbons, Datatype-Generic Programming |
Jeremy Gibbons demonstrates that four Gang of Four design patterns are captured by the recursion operators of Origami Programming:
Since the recursive type Fix
captures a whole class of recursive datatypes, Fix
captures the composite pattern most concisely.
In Chapter 4, Patterns of Folding and Traversing, we discussed how the iterator pattern is captured most generally by applicative traversals.
We can construct generic applicative traversals in the origami style we have seen here, and thereby capture the iterator pattern.
fold
enables.The generic fold function allows us to visit the elements of a Composite pattern. Visitor, like fold, does not generally preserve the shape of the data structure being visited. This is why it is said that an Iterator views a composite structure as a "container of elements", while a Visitor views the shape of a composite as insignificant.
We can express the structured construction of data structures with unfold
. The hybrid hylo
function (unfold
+ fold
) also allows for data generation. In this way the origami style captures the Builder pattern.