### 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
= IfThenElse (input -> Bool) (BusinessRule input output) (BusinessRule input output)
| Return (input -> output)
| Stop
```

`Functor`

`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 effectsDerivable using

`DeriveTraversable`

language pragmaSee '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
```