## Sunday, December 31, 2017

### N-ary Functors

update: Now available on hackage as `n-ary-functor`.

`Functor` and `Bifunctor` are both in `base`, but what about `Trifunctor`? `Quadrifunctor`? There must be a better solution than creating an infinite tower of typeclasses. Here's the API I managed to implement:

``````> nmap <#> (+1) <#> (+2) \$ (0, 0)
(1,2)

> nmap <#> (+1) <#> (+2) <#> (+3) \$ (0, 0, 0)
(1,2,3)

> nmap <#> (+1) <#> (+2) <#> (+3) <#> (+4) \$ (0, 0, 0, 0)
(1,2,3,4)``````

The implementation is really short, too:

``````{-# LANGUAGE RankNTypes, TypeFamilies, TypeInType #-}
import Data.Kind

newtype NMap1 k (f :: Type -> k) (g :: Type -> k) = NMap1
{ (<#>) :: forall a b. (a -> b) -> NMap k (f a) (g b) }

type family NMap k :: k -> k -> Type where
NMap Type        = (->)
NMap (Type -> k) = NMap1 k

class NFunctor (f :: k) where
nmap :: NMap k f f``````

Of course, the hard part is not writing the code, but figuring out what to write down. Let me show you how I got there.

#### Computing the Type from the Kind

Since `Functor` instances are given to type constructors of kind `* -> *`, and `Bifunctor` instances are given to type constructors of kind `* -> * -> *`, my idea was to compute the type of `nmap` from the kind of the type constructor to which it is applied. Something like this:

``````class NFunctor (f :: k) where
nmap :: NMap k f

type family NMap k (f :: k) :: *
type instance NMap (* -> *) f
= (a -> b) -> f a -> f b
type instance NMap (* -> * -> *) f
= (a1 -> b1) -> (a2 -> b2) -> f a1 a2 -> f b1 b2
type instance NMap (* -> * -> * -> *) f
= (a1 -> b1) -> (a2 -> b2) -> (a3 -> b3) -> f a1 a2 a3 -> f b1 b2 b3``````

Except of course with some recursive definition for `NMap`, so we don't have to spell out the type for every kind. Thinking of it in terms of recursion made me realize that the base case is kind `*`, not `* -> *`:

``````type instance NMap * f
= f -> f``````

This corresponds to a "nullary Functor" typeclass, whose lawful instances have no choice but to use the identity function. So this isn't particularly useful as a typeclass, but it does lead to a nice recursive definition:

``````type family NMap k (f :: k) (g :: k) where
NMap Type        a b = a -> b
NMap (Type -> k) f g = (a -> b) -> NMap k (f a) (g b)

class NFunctor (f :: k) where
nmap :: NMap k f f``````

I now have to use `Type` instead of `*` for some reason, otherwise I get a "malformed head" error.

#### Required Newtype Wrapper

Unfortunately, GHC does not accept that recursive definition. First of all, when defining a type family, type variables aren't implicitly universally-quantified like they are in type signatures, so I need to add an explicit `forall` quantifier:

``````type family NMap k (f :: k) (g :: k) where
NMap Type        a b = a -> b
NMap (Type -> k) f g = forall a b. (a -> b) -> NMap k (f a) (g b)``````

Now GHC reveals the real problem with the definition:

``````• Illegal polymorphic type:
forall a b. (a -> b) -> NMap k (f a) (g b)
• In the equations for closed type family ‘NMap’
In the type family declaration for ‘NMap’``````

This is a bummer: I am simply not allowed to use `forall` here. The usual workaround, when `forall` is needed but disallowed, is to define a newtype which performs the `forall` for us:

``````newtype NMap1 k (f :: Type -> k) (g :: Type -> k) = NMap1
{ runNMap1 :: forall a b. (a -> b) -> NMap k (f a) (g b) }

type family NMap k :: k -> k -> Type where
NMap Type        = (->)
NMap (Type -> k) = NMap1 k``````

This solves the problem, and even allows me to make my `NMap` definition more point-free!

#### Ergonomics

I now have a typeclass which generalizes `Functor`, `Bifunctor`, `Trifunctor`, etc., but what does using this typeclass look like? Writing instances requires a bit of boilerplate, but it's not too bad:

``````instance NFunctor Maybe where
nmap = NMap1 fmap

instance NFunctor (,) where
nmap = NMap1 \$ \f1
-> NMap1 \$ \f2
-> \(x1,x2)
-> (f1 x1, f2 x2)

instance NFunctor (,,) where
nmap = NMap1 \$ \f1
-> NMap1 \$ \f2
-> NMap1 \$ \f3
-> \(x1,x2,x3)
-> (f1 x1, f2 x2, f3 x3)

instance NFunctor (,,,) where
nmap = NMap1 \$ \f1
-> NMap1 \$ \f2
-> NMap1 \$ \f3
-> NMap1 \$ \f4
-> \(x1,x2,x3,x4)
-> (f1 x1, f2 x2, f3 x3, f4 x4)``````

When calling `nmap`, however, the extra boilerplate quickly becomes annoying:

``````> runNMap1 nmap (+1) \$ Just (0)
Just 1

> runNMap1 (runNMap1 nmap (+1)) (+2) (0, 0)
(1,2)

> runNMap1 (runNMap1 (runNMap1 nmap (+1)) (+2)) (+3) (0, 0, 0)
(1,2,3)

> runNMap1 (runNMap1 (runNMap1 (runNMap1 nmap (+1))
|                              (+2))
|                    (+3))
|          (+4)
|          (0, 0, 0, 0)
(1,2,3,4)``````

The fix is really simple though: by renaming `runNMap1` to some left-associative infix operator, say `(<#>)`, the code becomes much more readable!

``````> nmap <#> (+1) \$ Just (0)
Just 1

> nmap <#> (+1) <#> (+2) \$ (0, 0)
(1,2)

> nmap <#> (+1) <#> (+2) <#> (+3) \$ (0, 0, 0)
(1,2,3)

> nmap <#> (+1) <#> (+2) <#> (+3) <#> (+4) \$ (0, 0, 0, 0)
(1,2,3,4)``````

#### A Tempting Overlapping Instance

Pairs have both a `Bifunctor` and a `Functor` instance. Similarly, quadruples have four `NFunctor` instances, five if we count the glorified identity function:

``````-- |
-- >>> nmap <#> (+1) <#> (+2) <#> (+3) <#> (+4) \$ (0, 0, 0, 0)
-- (1,2,3,4)
instance NFunctor (,,,) where
nmap = NMap1 \$ \f1
-> NMap1 \$ \f2
-> NMap1 \$ \f3
-> NMap1 \$ \f4
-> \(x1,x2,x3,x4)
-> (f1 x1, f2 x2, f3 x3, f4 x4)

-- |
-- >>> nmap <#> (+1) <#> (+2) <#> (+3) \$ (0, 0, 0, 0)
-- (0,1,2,3)
instance NFunctor ((,,,) a) where
nmap = NMap1 \$ \f2
-> NMap1 \$ \f3
-> NMap1 \$ \f4
-> \(x1,x2,x3,x4)
-> (x1, f2 x2, f3 x3, f4 x4)

-- |
-- >>> nmap <#> (+1) <#> (+2) \$ (0, 0, 0, 0)
-- (0,0,1,2)
instance NFunctor ((,,,) a b) where
nmap = NMap1 \$ \f3
-> NMap1 \$ \f4
-> \(x1,x2,x3,x4)
-> (x1, x2, f3 x3, f4 x4)

-- |
-- >>> nmap <#> (+1) \$ (0, 0, 0, 0)
-- (0,0,0,1)
instance NFunctor ((,,,) a b c) where
nmap = NMap1 \$ \f4
-> \(x1,x2,x3,x4)
-> (x1, x2, x3, f4 x4)

-- |
-- >>> nmap (0, 0, 0, 0)
-- (0,0,0,0)
instance NFunctor ((,,,) a b c d) where
nmap = \(x1,x2,x3,x4)
-> (x1, x2, x3, x4)``````

But if we define the following magical instance:

``````{-# LANGUAGE FlexibleInstances #-}

instance NFunctor (f :: * -> k) => NFunctor (f a) where
nmap = nmap <#> id``````

Then we get all five instances for the price of one!

``````-- |
-- >>> nmap <#> (+1) <#> (+2) <#> (+3) <#> (+4) \$ (0, 0, 0, 0)
-- (1,2,3,4)
-- >>> nmap <#> (+1) <#> (+2) <#> (+3) \$ (0, 0, 0, 0)
-- (0,1,2,3)
-- >>> nmap <#> (+1) <#> (+2) \$ (0, 0, 0, 0)
-- (0,0,1,2)
-- >>> nmap <#> (+1) \$ (0, 0, 0, 0)
-- (0,0,0,1)
-- >>> nmap (0, 0, 0, 0)
-- (0,0,0,0)
instance NFunctor (,,,) where
nmap = NMap1 \$ \f1
-> NMap1 \$ \f2
-> NMap1 \$ \f3
-> NMap1 \$ \f4
-> \(x1,x2,x3,x4)
-> (f1 x1, f2 x2, f3 x3, f4 x4)``````

The big problem with that magic instance is that it overlaps with other instances we would like to define. For example, we don't want to define the `NFunctor` instance for `State s` in terms of the `NFunctor` instance for `State`, because `State` is not functorial in `s`, so it doesn't have such an instance. Oh well.

:: said...

It's absolutely impossible to read Your blog due to markup: post block is super narrow and code snippets are out of the block!

Post is interesting, but... ;)

gelisam said...

In which OS and browser are you reading it? Have you tried zooming in?

The narrow body forces me to make sure the lines of my code snippets aren't too wide, so they don't wrap around on mobile (in landscape mode at least). So if they still display outside of the narrow body despite all my efforts, something is very wrong.