This post is rendered from literate Haskell. I recommend doing the exercises inline, so use the source.

> *{-# LANGUAGE DeriveFunctor
> , DeriveFoldable
> , DeriveTraversable
> , TypeOperators #-}*
>
> __import__ Control.Applicative
> __import__ Data.Foldable
> __import__ Data.Traversable

Certain kinds of typeclasses have some very regular instances. For example, it is obvious how to implement `(Num a, Num b) => Num (a,b)`

and `(Monoid a, Monoid b) => Monoid (a,b)`

, and similarly if `F`

is some applicative functor, `(Num a) => Num (F a)`

and `(Monoid a) => (Monoid F a)`

are obvious. Furthermore, these instances (and many others) seem to be obvious in the same way.

```
(+) a b = (+) <$> a <*> b
mappend a b = mappend <$> a <*> b
fromInteger n = pure (fromInteger n)
mempty = pure mempty
```

And take them on pairs:

```
(x,x') + (y,y') = (x + y, x' + y')
(x,x') `mappend` (y,y') = (x `mappend` y, x' `mappend` y')
fromInteger n = (fromInteger n, fromInteger n)
mempty = (mempty , mempty)
```

It would be straightforward for these cases to derive the necessary implementations from the type signature. However, it would be nice if there were a more abstract perspective, such that we didn’t have to inspect the type signature to find the operations – that they could arise from some other standard construction. Further, it is not quite as obvious from the the type signature how to automatically instantiate methods such as

`mconcat :: (Monoid m) => [m] -> m`

without making a special case for `[]`

, whereas hopefully a more abstract perspective would inform us what kinds of type constructors would be supported.

In this post, we will see such an abstract perspective. It comes from (surprise!) category theory. I disclaim that I’m still a novice with category theory (but in the past few weeks I have gained competence by studying). So we will not get very deep into the theory, just enough to steal the useful concept and leave the rest behind. I welcome relevant insights from the more categorically educated in the comments.

## F-Algebras

The unifying concept we will steal is the *F-algebra*. An F-algebra is a Functor `f`

and a type `a`

together with a function `f a -> a`

. We can make this precise in Haskell:

> __type__ Algebra f a = f a -> a

I claim that `Num`

and `Monoid`

instances are F-algebras over suitable functors. Look at the methods of `Monoid`

:

```
mempty :: m
mappend :: m -> m -> m
```

We need to find a functor `f`

such that we can recover these two methods from a function of type `f m -> m`

. With some squinting, we arrive at:

> __data__ MonoidF m
> = MEmpty
> | MAppend m m
>
> memptyF :: Algebra MonoidF m -> m
> memptyF alg = alg MEmpty
>
> mappendF :: Algebra MonoidF m -> (m -> m -> m)
> mappendF alg x y = alg (MAppend x y)

**Exercise 1:** work out the functor `NumF`

over which `Num`

instances are F-algebras, and write the methods of `Num`

in terms of it.

**Exercise 2:** for each of the standard classes `Eq`

, `Read`

, `Show`

, `Bounded`

, and `Integral`

, work out whether they are expressible as F-algebras. If so, give the functor; if not, explain or prove why not.

**Exercise 3:** write a function `toMonoidAlg`

which finds the `MonoidF`

-algebra for a given instance `m`

of the `Monoid`

class.

## Combining Instances

Motivated by the examples in the introduction, we can find the “instance” for pairs given instances for each of the components.

> pairAlg :: (Functor t) => Algebra t a -> Algebra t b -> Algebra t (a,b)
> pairAlg alga algb tab = (alga (fmap fst tab), algb (fmap snd tab))

Also, we hope we can find the instance for an applicative functor given an instance for its argument

```
applicativeAlg :: (Functor t, Applicative f)
=> Algebra t a -> Algebra t (f a)
```

but there turns out to be trouble:

`applicativeAlg alg tfa = ...`

We need to get our hands on an `t a`

somehow, and all we have is a `t (f a)`

. This hints at something from the standard library:

`sequenceA :: (Traversible t, Applicative f) => t (f a) -> f (t a)`

which indicates that our functor needs more structure to implement `applicativeAlg`

.

> applicativeAlg :: (Traversable t, Applicative f)
> => Algebra t a -> Algebra t (f a)
> applicativeAlg alg tfa = fmap alg (sequenceA tfa)

Now we should be able to answer the query from the beginning:

**Exercise 4:** For what kinds of type constructors `c`

is it possible to automatically derive instances for *(a)* pairs and *(b)* `Applicative`

s for a typeclass with a method of type `c a -> a`

. (e.g. `mconcat :: [a] -> a`

). Demonstrate this with an implementation.

## Combining Classes

Intuitively, joining the methods of two classes which are both expressible as F-algebras should give us another class expressible as an F-algebra. This is demonstrated by the following construction:

> __data__ (f **:+:** g) a = InL (f a) | InR (g a)
> __deriving__ (Functor, Foldable, Traversable)
>
> coproductAlg :: (Functor f, Functor g)
> => Algebra f a -> Algebra g a -> Algebra (f **:+:** g) a
> coproductAlg falg _____ (InL fa) = falg fa
> coproductAlg _____ galg (InR ga) = galg ga

So now we can model a subclass of both `Num`

and `Monoid`

by `type NumMonoidF = NumF :+: MonoidF`

.

**Exercise 5:** We hope to be able to recover `Algebra NumF a`

from `Algebra NumMonoidF a`

, demonstrating that the latter is in fact a subclass. Implement the necessary function(s).

**Exercise 6:** Given the functor product definition

> __data__ (f **:*:** g) a = Pair (f a) (g a)
> __deriving__ (Functor, Foldable, Traversable)

find a suitable combinator for forming algebras over a product functor. It may not have the same form as coproduct’s combinator! What would a typeclass formed by a product of two typeclasses interpreted as F-algebras look like?

## Free Constructions

One of the neat things we can do with typeclasses expressed as F-algebras is form free monads over them – i.e. form the data type of a “syntax tree” over the methods of a class (with a given set of free variables). Begin with the free monad over a functor:

> __data__ Free f a
> = Pure a
> | Effect (f (Free f a))
> __deriving__ (Functor, Foldable, Traversable)
>
> __instance__ (Functor f) => Monad (Free f) __where__
> return = Pure
> Pure a >>= t = t a
> Effect f >>= t = Effect (fmap (>>= t) f)

(Church-encoding this gives better performance, but I’m using this version for expository purposes)

`Free f a`

can be interpreted as a syntax tree over the typeclass formed by `f`

with free variables in `a`

. This is also called an “initial algebra”, a term you may have heard thrown around in the Haskell community from time to time. We demonstrate that a free construction over a functor is a valid F-algebra for that functor:

> initialAlgebra :: (Functor f) => Algebra f (Free f a)
> initialAlgebra = Effect

And that it is possible to “interpret” an initial algebra using any other F-algebra over that functor.

> initiality :: (Functor f) => Algebra f a -> Free f a -> a
> initiality alg (Pure a) = a
> initiality alg (Effect f) = alg (fmap (initiality alg) f)

**Exercise 7:** Give a monoid isomorphism (a bijection that preserves the monoid operations) between `Free MonoidF`

and lists `[]`

, ignoring that Haskell allows infinitely large terms. Then, using an infinite term, show how this isomorphism fails.

*Next time: F-Coalgebras*