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.