# Haskell Language Functor Polynomial functors

## Example

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

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

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.

## Functor products

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.

## Functor coproducts

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.

## Functor composition

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`

## Polynomial functors for generic programming

`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.

NameAs a datatypeUsing 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
`````` PDF - Download Haskell Language for free