# From Zero to Comp Data, Part 2: Base Functors

24 Jul 2013

As of March 2020, School of Haskell has been switched to read-only mode.

### Sections

In the introduction I opened with the question "What are recursive data types, really?". Let's start to break that down here.

We'll first explore one mathematically natural definition---though there are other perspectives, especially for Haskell's data types---that a recursive data type is an initial `F`-algebra for some base functor `F`.

Without trying to define that notion yet, let's just take it as a guide that base functors, whatever they are, are important.

## Base functors

Base functors let us extract from a recursive data type a non-recursive piece. We'll later see that the remaining recursive bits are generic and it is this non-recursive piece that forms the nature of a recursive data type. You might say that base functors are simple lenses which refract essential recursion into the various shapes we need.

Immediately, here are some example recursive data types and their base functors.

``````-- numbers
data Nat    = Zero | Succ Nat
data NatF a = Zero | Succ a

instance Functor NatF where
fmap f Zero     = Zero
fmap f (Succ a) = Succ (f a)

-- lists
data List  b   = Nil | Cons b (List a)
data ListF b a = Nil | Cons b a

instance Functor (ListF b) where
fmap f Nil = Nil
fmap f (Cons b a) = Cons b (fmap f a)

-- n-ary trees
data Tree  b   = Branch b [Tree b]
data TreeF b a = Branch b [a]

instance Functor (TreeF b) where
fmap f (Branch b as) = Branch b (map f as)``````

For these simple patterns, the idea ought to be obvious enough. We add an extra type parameter, here called `a`, which replaces the recursive name in each data type. Note that technically `TreeF` is still recursive since it uses `[]`, a recursive data type in itself. We could technically extend the base functor notion to remove all recursiveness, but for simplicity we'll just ignore it for now.

There is one complexity when we consider `ListF` and `TreeF`, though, in that we're used to them being functors over the type parameter `b`. While it's not yet clear why, we've given them `Functor` instances over the new parameter. This is a clear mismatch from the data type the each base is supposed to somehow represent. We'll want that original `Functor` behavior later, though, so we'll create a new typeclass for data types which could be functors on two type parameters.

``````-- a functor on two type arguments
class Bifunctor f where
bimap :: (b -> b') -> (a -> a') -> f b a -> f b' a'

instance Bifunctor TreeF where
bimap f g (Branch b as) = Branch (f b) (map g as)``````

It's worth noting that `Bifunctor` could be extended to `Trifunctor` and `Quadrafunctor` and so on---while Haskell makes it appear that parameter position is important, `Bifunctor` makes it clear that with types like `TreeF` we can "lift" functions up into any of the parameter slots. When we do, each lifting simply acts independently.

### When is a functor not a `Functor`?

At this point, it's a good idea to take a short digression into a kind of parallel univese of `Functor`s and examine the friction between mathematical functors and Haskell `Functor` instances. Consider the `Reader` functor which represents the computation of a value `a` in the context of a value `b`.

``````data Reader b a = Reader (b -> a)

instance Functor (Reader b) where
-- transform our result by *composing* a function
fmap f (Reader g) = Reader (f . g)``````

This is clearly a `Functor`, but it has an extra type parameter like `TreeF` above. Is it also a `Bifunctor`?

The answer is no, it cannot be. It is instead what's known mathematically as a "contravariant functor", which is like a functor but backwards.

``````class Contravariant f where
--           a-to-b becomes... b-to-a?
contramap :: (a -> b) -> (f b -> f a)``````

So, a `Contravariant` functor is "a functor that reverses arrows". Generally, all data types are either covariant `Functor`s, `Contravariant` functors, or both in each of their arguments. We can talk fluently about these variances if we use the notation `+` to represent a covariant position, `-` to represent a contravariant position, and `?` to represent an "impartial" position. In this notation we can annotate some functors

``````TreeF  b a   ~~~>    TreeF  + +
ListF  b a   ~~~>    ListF  + +
Reader b a   ~~~>    Reader - +

data Const b a = Const b -- ignores its second parameter
~~~> Const + ?``````

When we write these, they're called a signature. The notation also suggest a method for determining the signature of any type. We begin by labeling result types as covariant (`+`), input types as contravariant (`-`), and unused types as `?`.

``````data F1 a b c d e f g = F1 (a -> c -> d | a -> b -> d )
~~~> F1 - - - + ? ? ?``````

Then, we just multiply the variances for compound types, like so

``````data F2 a b c d e = F2 (  (a -> b) -> c | F1 d d d e e e e )
= F2 ( -(- -> +) -> + | F1 - - - + ? ? ? )
= F2 (  (+ -> -) -> + | F1 - - - + ? ? ? )
~~~> F2 + - + - +``````

where `?` multiplied by `-` or `+` is just `-` or `+` respectively.

Since `Reader` has signature `Reader - +`, we can make it a `Functor`, we can make "flipped reader" a `Contravariant` functor, or we can make `Reader` itself a `Profunctor`, which is the name for a functor of signature `- +`.

``````data FlippedReader a b = FlippedReader (b -> a)

instance Contravariant (FlippedReader a) where
-- precompose our function, making the reader take a new kind of argument
contramap f (FlippedReader g) = FlippedReader (f . g)

class Profunctor f where
promap :: (b -> b') -> (a -> a') -> (f b' a -> f b a')

instance Profunctor Reader where
promap f g (Reader h) = Reader (g . h . f)``````

## Recap

We've examined recursive data types and taken note of a way to simplify recursive datatypes into their deflated base functors. Next we'll reinflate base functors to recapture recursive data types, and begin to explore what that separation gives us.

We've also explored the notion of a functor a bit to learn about variance signatures. Variance signatures are useful tool for describing functors and functors of different signatures will be important later.

### Questions

1. Can we form base functors for more exotic data types? Consider

``` data X c b = X1 c | X2 (X c b -> b) ```

What is `X`'s base functor? What is its signature?

2. What is the base functor of `Tree b` eliminating both the `Tree` recursion and the `[]` recursion?

3. What happens if a type parameter is both contravariant and covariant? How can we extend the notation and method to handle this case?

4. Since `Reader` cannot be a `Bifunctor` instance, but it's still a mathematical functor, what would a typeclass a functor like `Reader` look like?