# Susan Potter

## Practical Recursion Schemes

### Recursive data types

Recursive data structures pop up all over in software from general-purpose structures like lists and binary trees to more application-specific structures like this AST from a simple business rules engine:

``````  data BusinessRule input output
| Return (input -> output)
| Stop``````

### `Foldable`

The `Foldable` class gives you the ability to process the elements of a structure one-at-a-time, discarding the shape.

Intuitively this is an assortment of `List`-like fold methods on other structures

``````class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
fold    :: Monoid m => t m -> m
foldr   :: (a -> b -> b) -> b -> t a -> b
foldl   :: (a -> b -> a) -> a -> t b -> a
foldr1  :: (a -> a -> a) -> t a -> a
foldl1  :: (a -> a -> a) -> t a -> a``````

Example of defining a `Foldable` instance manually:

``````data Tree a
= Empty
| Leaf a
| Node (Tree a) (Tree a)

instance Foldable Tree where
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node l r) = foldMap f l <> foldMap f r

count :: Foldable t => t a -> Int
count = getSum . foldMap (const \$ Sum 1)``````

`Foldable` is derivable using the `DeriveFoldable` language pragma like so:

``````data Tree a
= Empty
| Leaf a
| Node (Tree a) (Tree a)
deriving (Foldable)``````

### Traversable

Traversable gives you the ability to traverse a structure from left-to-right, performing an effectful action on each element and preserving the shape.

• Intuitively it is `fmap` with effects

• Derivable using `DeriveTraversable` language pragma

• See 'Applicative Progamming with Effects', by McBride and Paterson

``````class (Functor t, Foldable t) => Traversable t where
traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
mapM      :: Monad m => (a -> m b) ->  t a ->  m (t a)
sequence  :: Monad m => t (m a) -> m (t a)``````

Example for this for `Tree` type defining the instance manually is:

``````instance Traversable Tree where
traverse f Empty = pure Empty
traverse f (Leaf x) = Leaf <\$> f x
traverse f (Node l r) = Node <\$> traverse f l <*> traverse f r``````

Notes:

• `mapM` and `sequence` generalize Prelude functions of the same name

• `sequence` can also be thought of as a generalized matrix transpose

``````sequence :: Monad m => t (m a) -> m (t a)
sequence = mapM id``````

### Fixed Points of Functors

An idea from category theory which gives:

• data-type generic functions

• compositional data

Fixed points are represented by the type:

``newtype Fix f = Fix { unFix :: f (Fix f) }``

A functor `f` is a data-type of kind `* -> *` together with an `fmap` function.

``Fix f = f (f (f (f ...``

### Useful functions

#### fan-out aka fork

``````(&&&)
:: (b -> c)
-> (b -> d)
-> b
-> (c, d)
(f &&& g) = \x -> (f x, g x)``````

#### fan-in

``````(|||)
:: (b -> d)
-> (c -> d)
-> Either b c
-> d
(f ||| g) = either``````

#### function product

``````(***)
:: (a -> c)
-> (b -> d)
-> (a, b)
-> (c, d)
(f *** g) = \(x, y) -> (f x, g y)``````

#### generalized unzip for functions

``````funzip
:: Functor f
=> f (a, b)
-> (f a, f b)
funzip = fmap fst &&& fmap snd``````

### Data-type generic programming

• allows us to parameterise functions on the structure, or shape, of a data-type

• useful for large complex data-types, where boilerplate traversal code often dominates, especially when updating a small subset of constructors

• for recursion schemes, we can capture the pattern as a standalone combinator

Limitations:

• The set of data-types that can be represented by means of `Fix` is limited to regular data-types.

• Nested data-types and mutually recursive data-types require higher-order approaches.

In order to work with lists using a data-type generic `cata` combinator, we need a new "unfixed" type representation.

``data ListF a r = C a r | N``

`ListF a r` is not an ordinary functor, but we can define a polymorphic functor instance for `ListF a`

``````instance Functor (ListF a) where
fmap f N = N
fmap f (C x xs) = C x (f xs)``````

We might also want a pattern functor for natural numbers!

``data NatF r = Succ r | Zero deriving Functor``

### Catamorphism

We would like to write `foldr` once for all data-types. Category theory shows us how to define it data-type generically for a functor fixed-point.

#### That catamorphism-fusion law

The catamorphism-fusion law is arguably the most important law, and can be used to transform the composition of a function with a catamorphism into a single catamorphism, eliminating intermediate data structures.

``````h . f = g . fmap h => h . cata f = cata g
where f :: f a -> a
g :: f b -> b
h :: a -> b``````