What are bifunctors?

Question

I'm relatively new to Haskell and having trouble understanding the utility of bifunctors. I think I understand them in theory: say for example if I wanted to map across a type that abstracts multiple concrete types, such as Either or Maybe, I'd need to encapsulate them in a bifunctor. But on the one hand, those examples seems particularly contrived, and on the other it does seem like you could achieve that same functionality simply through composition.

As an example, I came across this code in The Essence of the Iterator Pattern by Jeremy Gibbons and Bruno C. d. S. Oliveira:

import Data.Bifunctor

data Fix s a = In {out::s a (Fix s a) }

map' :: Bifunctor s => (a -> b) -> Fix s a -> Fix s b
map' f = In . bimap f (map' f) . out

fold' :: Bifunctor s => (s a b -> b) -> Fix s a -> b
fold' f = f . bimap id (fold' f) . out

unfold' :: Bifunctor s => (b -> s a b) -> b -> Fix s a
unfold' f = In . bimap id (unfold' f) . f

I understand the point is to compose mapping and folding functions to create an iterator pattern and this is achieved by defining a data constructor that requires two parameters. But in practice I don't understand how this is any different then using a regular functor and composing the functions with fmap instead of bimap. I think I clearly must be missing something, both with this example and, likely, in general.

Benjamin Hodgson Benjamin Hodgson · Accepted Answer · 2016-12-10T12:55:27

I think you're overthinking it slightly. A bifunctor is just like a two-parameter functor. Gibbons and Oliveira's idea is just one application of bifunctors, just like the standard zoo of recursion schemes is just one application of functors.

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d

Bifunctors have a kind of * -> * -> * and both parameters can be covariantly mapped over. Compare this to regular Functors, which have only one parameter (f :: * -> *) which can be covariantly mapped over.

For example, think about Either's usual Functor instance. It only allows you to fmap over the second type parameter - Right values get mapped, Left values stay as they are.

instance Functor (Either a) where
    fmap f (Left x) = Left x
    fmap f (Right y) = Right (f y)

However, its Bifunctor instance allows you to map both halves of the sum.

instance Bifunctor Either where
    bimap f g (Left x) = Left (f x)
    bimap f g (Right y) = Right (g y)

Likewise for tuples: (,)'s Functor instance allows you to map only the second component, but Bifunctor allows you to map both parts.

instance Functor ((,) a) where
    fmap f (x, y) = (x, f y)

instance Bifunctor (,) where
    bimap f g (x, y) = (f x, g y)

Note that Maybe, which you mentioned, doesn't fit into the framework of bifunctors because it has only one parameter.

On the question of Fix, the fixed point of a bifunctor allows you to characterise recursive types which have a functorial type parameter, such as most container-like structures. Let's use lists as an example.

newtype Fix f = Fix { unFix :: f (Fix f) }

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

Using the standard functorial Fix, as I have above, there's no generic derivation of an instance of Functor for List, because Fix doesn't know anything about List's a parameter. That is, I can't write anything like instance Something f => Functor (Fix f) because Fix has the wrong kind. I have to hand-crank a map for lists, perhaps using cata:

map :: (a -> b) -> List a -> List b
map f = cata phi
    where phi Nil_ = Fix Nil_
          phi Cons_ x r = Fix $ Cons_ (f x) r

The bifunctorial version of Fix does permit an instance of Functor. Fix uses one of the bifunctor's parameters to plug in the recursive occurrence of Fix f a and the other one to stand in for the resultant datatype's functorial parameter.

newtype Fix f a = Fix { unFix :: f a (Fix f a) }

instance Bifunctor f => Functor (Fix f) where
    fmap f = Fix . bimap f (fmap f) . unFix

So we can write:

deriveBifunctor ''ListF

type List = Fix ListF

and get the Functor instance for free:

map :: (a -> b) -> List a -> List b
map = fmap

Of course, if you want to work generically with recursive structures with more than one parameter then you need to generalise to tri-functors, quad-functors, etc... This is clearly not sustainable, and plenty of work (in more advanced programming languages) has been put into designing more flexible systems for characterising types.

What are bifunctors?

1 Answers