Due to kind restrictions, the Haskell Functor cannot represent a lot of valid functors: functors of higher kinded types (higher than * -> *), contravariant functors, invariant functors, etc.

This post will show an alternate Functor that can handle all of the above. I got this idea from the awesome Tom Harding, and he apparently got it from @Iceland_jack.

Although this is not new, I could not find any blog post or paper covering it.

The actual problem

The problem is quite straight-forward. Let's say we want to define a functor instance for (a, b) which changes the a, to c using an a -> c function. This should be possible, but there is no way to write it using Functor and fmap.

There are two ways to do this in Haskell using Prelude: - by using Bifunctor/first, or - by using the Flip newtype.

While both the above options work, they are not particularly elegant. On top of that, there is no common Trifunctor package, and flipping arguments around and wrapping/unwrapping newtypes is not very appealing, which means the approach doesn't quite scale well.

FunctorOf to the rescue

There are two problems with Functor: - f has the wrong kind if we want to allow higher kinded functors, and - the arrow of the mapped function is the wrong type if we want to allow contravariant or invariant functors (or even other types of mappings!).

We can fix both problems by adding additional types to the class:

class FunctorOf (p :: k -> k -> Type) (q :: l -> l -> Type) f where
  map :: p a b -> q (f a) (f b)

p represents a relationshiop (arrow) between a and b. In case of a regular functor, it's just ->, but we can change it to a reverse arrow for contravariants.

q is normally just an optional layer on top of ->, in order to allow mapping over other arguments. For example, if we want to map over the second-to-last argument, we'd use natural transforms (~>).

The regular functor instance can be obtained by simply:

instance Functor f => FunctorOf (->) (->) f where
  map :: forall a b. (a -> b) -> f a -> f b
  map = fmap

functorExample :: [String]
functorExample = map show ([1, 2, 3, 4] :: [Int])

Functor for HKD

I'll use the Bifunctor instance in order to show all bifunctors can have such a FunctorOf instance. Of course, one could define instances manually for any Bifunctor.

Going back to our original example, we can define a FunctorOf instance for * -> * -> * types in the first argument via:

newtype (~>) f g = Natural (forall x. f x -> g x)
  
instance Bifunctor f => FunctorOf (->) (~>) f where
  map :: forall a b. (a -> b) -> f a ~> f b
  map f = Natural $ first f

In order to avoid fiddling about with newtypes, we can define a helper bimap' function for * -> * -> * that maps both arguments:

bimap'
  :: forall a b c d f
  .  FunctorOf (->) (->) (f a)
  => FunctorOf (->) (~>) f
  => (a -> b)
  -> (c -> d)
  -> f a c
  -> f b d
bimap' f g fac =
  case map f of
    Natural a2b -> a2b (map g fac)

bifunctorExample :: (String, String)
bifunctorExample = bimap' show show (1 :: Int, 1 :: Int)

Contravariant

Okay, cool. But what about contravariant functors? We can use Op from Data.Functor.Contravariant (defined as data Op a b = Op (b -> a)):

instance Contravariant f => FunctorOf Op (->) f where
  map :: forall a b. (Op b a) -> f b -> f a
  map (Op f) = contramap f

This is pretty cool since we only need to change the mapped function's type to be Op instead of ->! As before, we can make things easier by defining a helper:

cmap
  :: forall a b f
  .  FunctorOf Op (->) f
  => (b -> a)
  -> f a
  -> f b
cmap f fa = map (Op f) fa

contraExample :: Predicate Int
contraExample = cmap show (Predicate (== "5"))

What about Profunctors?

I'm glad you asked! It's as easy as 1-2-3, or well, as easy as "functor in the last argument" - "contravariant in the previous" - "write helper function":

instance Profunctor p => FunctorOf Op (~>) p where
  map :: forall a b. (Op b a) -> p b ~> p a
  map (Op f) = Natural $ lmap f

dimap'
  :: forall a b c d p
  .  FunctorOf (->) (->) (p a)
  => FunctorOf Op   (~>) p
  => (b -> a)
  -> (c -> d)
  -> p a c
  -> p b d
dimap' f g pac =
  case map (Op f) of
    Natural b2a -> b2a (map g pac)

profunctorExample :: String -> String
profunctorExample = dimap' read show (+ (1 :: Int))

Tri..functors?

Yep. We only need to define a higher-kinded natural transform and write the FunctorOf instance, along with the helper:

newtype (~~>) f g = NatNat (forall x. f x ~> g x)

data Triple a b c = Triple a b c deriving (Functor)

instance {-# overlapping #-} FunctorOf (->) (~>) (Triple x) where
  map :: forall a b. (a -> b) -> Triple x a ~> Triple x b
  map f = Natural $ \(Triple x a y) -> Triple x (f a) y

instance FunctorOf (->) (~~>) Triple where
  map :: (a -> b) -> Triple a ~~> Triple b
  map f = NatNat $ Natural $ \(Triple a x y) -> Triple (f a) x y

triple
  :: forall a b c d e f t
  .  FunctorOf (->) (->)  (t a c)
  => FunctorOf (->) (~>)  (t a)
  => FunctorOf (->) (~~>) t
  => (a -> b)
  -> (c -> d)
  -> (e -> f)
  -> t a c e
  -> t b d f
triple f g h = a2b . c2d . map h
  where
    (Natural c2d) = map g
    (NatNat (Natural a2b)) = map f

tripleExample :: Triple String String String
tripleExample = triple show show show (Triple (1 :: Int) (2 :: Int) (3 :: Int))

The pattern is pretty simple: - we need a FunctorOf instance for every argument we want to map - for each such argument, we need to use -> for variant and Op for contravariant arguments as the first argument to FunctorOf - from right to left, we need to use increasing level of transforms to map the type arguments (->, ~>, ~~>, etc)

What about invariants?

We can define an instance for Endo using:

data Iso a b = Iso
  { to   :: a -> b
  , from :: b -> a
  }

instance FunctorOf Iso (->) Endo where
  map :: forall a b. Iso a b -> Endo a -> Endo b
  map Iso { to, from } (Endo f) = Endo $ to . f . from

endoExample :: Endo String
endoExample = map (Iso show read) (Endo (+ (1 :: Int)))

We can even go further:

instance FunctorOf (->) (->) f => FunctorOf Iso Iso f where
  map :: Iso a b -> Iso (f a) (f b)
  map Iso { to, from } = Iso (map to) (map from)

which is to say, given an isomorphism between a and b, we can obtain an isomorphism between f a and f b!

Future work ideas

I think this instance can be also used for proofs. For example, using the Refl equality type:

data x :~: y where
  Refl :: x :~: x

And this means we can write transitivity as:

instance FunctorOf (:~:) (->) ((:~:) x) where
  map :: forall a b. a :~: b -> x :~: a -> x :~: b
  map Refl Refl = Refl

proof :: Int :~: String -> Bool :~: Int -> Bool :~: String
proof = map

Code is available here.

Another thing worth mentioning is the awesome upcoming GHC extension (being worked on by Csongor Kiss) which allows type families to be partially applied. If you haven't read the paper, you should! Using this feature, one could do something like:

type family Id a where Id x = x

instance FunctorOf (->) (->) Id
  map = ($)

idExample :: Bool
idExample = map (+1) 1 == 2

Please note I have not tested the above code; it was suggested by Tom Harding (thanks again for the idea and reviewing!).

What other uses can you come up with?