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 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
The constant functor ignores its second argument, containing only a constant value. It's a type-level analogue of
K combinator from SKI calculus.
newtype K c a = K c
K c a doesn't contain any
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
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
(:*:) :: (* -> *) -> (* -> *) -> (* -> *) operates on
* -> *.
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
:*: is analogous to
:+: is the functor-level analogue of
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
:.: 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)
Compose type can be found in
:.: 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|
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