Haskell Language Functor Polynomial functors
Example
There's a useful set of type combinators for building big Functors 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.
| 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
