Haskell Language Polynomial functors


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.

NameAs a datatypeUsing the functor kit
Pairs of valuesdata Pair a = Pair a atype Pair = I :*: I
Two-by-two gridstype Grid a = Pair (Pair a)type Grid = Pair :.: Pair
Natural numbersdata Nat = Zero | Succ Nattype Nat = Fix (K () :+: I)
Listsdata List a = Nil | Cons a (List a)type List a = Fix (K () :+: K a :*: I)
Binary treesdata Tree a = Leaf | Node (Tree a) a (Tree a)type Tree a = Fix (K () :+: I :*: K a :*: I)
Rose treesdata 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