**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.