There's a useful set of type combinators for building big `Functor`

s out of smaller ones. These are instructive as example instances of `Functor`

, and they're also useful as a technique for generic programming, because they can be used to represent a large class of common functors.

The identity functor simply wraps up its argument. It's a type-level implementation of the `I`

combinator from SKI calculus.

```
newtype I a = I a
instance Functor I where
fmap f (I x) = I (f x)
```

`I`

can be found, under the name of `Identity`

, in the `Data.Functor.Identity`

module.

The constant functor ignores its second argument, containing only a constant value. It's a type-level analogue of `const`

, the `K`

combinator from SKI calculus.

```
newtype K c a = K c
```

Note that `K c a`

doesn't contain any `a`

-values; `K ()`

is isomorphic to `Proxy`

. This means that `K`

's implementation of `fmap`

doesn't do any mapping at all!

```
instance Functor (K c) where
fmap _ (K c) = K c
```

`K`

is otherwise known as `Const`

, from `Data.Functor.Const`

.

The remaining functors in this example combine smaller functors into bigger ones.

The functor product takes a pair of functors and packs them up. It's analogous to a tuple, except that while `(,) :: * -> * -> *`

operates on `types`

`*`

, `(:*:) :: (* -> *) -> (* -> *) -> (* -> *)`

operates on `functors`

`* -> *`

.

```
infixl 7 :*:
data (f :*: g) a = f a :*: g a
instance (Functor f, Functor g) => Functor (f :*: g) where
fmap f (fx :*: gy) = fmap f fx :*: fmap f gy
```

This type can be found, under the name `Product`

, in the `Data.Functor.Product`

module.

Just like `:*:`

is analogous to `(,)`

, `:+:`

is the functor-level analogue of `Either`

.

```
infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)
instance (Functor f, Functor g) => Functor (f :+: g) where
fmap f (InL fx) = InL (fmap f fx)
fmap f (InR gy) = InR (fmap f gy)
```

`:+:`

can be found under the name `Sum`

, in the `Data.Functor.Sum`

module.

Finally, `:.:`

works like a type-level `(.)`

, taking the output of one functor and plumbing it into the input of another.

```
infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))
instance (Functor f, Functor g) => Functor (f :.: g) where
fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)
```

The `Compose`

type can be found in `Data.Functor.Compose`

`I`

, `K`

, `:*:`

, `:+:`

and `:.:`

can be thought of as a kit of building blocks for a certain class of simple datatypes. The kit becomes especially powerful when you combine it with fixed points because datatypes built with these combinators are automatically instances of `Functor`

. You use the kit to build a template type, marking recursive points using `I`

, and then plug it into `Fix`

to get a type that can be used with the standard zoo of recursion schemes.

Name | As a datatype | Using the functor kit |
---|---|---|

Pairs of values | `data Pair a = Pair a a` | `type Pair = I :*: I` |

Two-by-two grids | `type Grid a = Pair (Pair a)` | `type Grid = Pair :.: Pair` |

Natural numbers | `data Nat = Zero | Succ Nat` | `type Nat = Fix (K () :+: I)` |

Lists | `data List a = Nil | Cons a (List a)` | `type List a = Fix (K () :+: K a :*: I)` |

Binary trees | `data Tree a = Leaf | Node (Tree a) a (Tree a)` | `type Tree a = Fix (K () :+: I :*: K a :*: I)` |

Rose trees | `data Rose a = Rose a (List (Rose a))` | `type Rose a = Fix (K a :*: List :.: I)` |

This "kit" approach to designing datatypes is the idea behind *generic programming* libraries such as `generics-sop`

. The idea is to write generic operations using a kit like the one presented above, and then use a type class to convert arbitrary datatypes to and from their generic representation:

```
class Generic a where
type Rep a -- a generic representation built using a kit
to :: a -> Rep a
from :: Rep a -> a
```