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.

Coloration

Answer 1

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.

Gleich

May I ask what sort of work in what sorts of programming languages? Can you point to something accessible? I've been thinking it might be possible to define something like class Covariant (n :: Nat) p expressing that p is covariant in its nth parameter, but I'm not quite sure what that would look like. – Bengali

Thanks for the clear explanation! I was thinking of bifunctors as superfluous syntactic sugar, but your example of overloading map to take two parameters demonstrates how they're actually much simpler semantically as well. I'm also intrigued by what you were referring to in your comment at the end, though. Doesn't OCaml have polymorphic functors? – Coloration

@Bengali Oh, I was just making reference to the constellation of "universe"-style datatype descriptions that have been developed in DT languages. – Gleich

@Bengali PS, thinking aloud here, but I think a "Covariant-in-parameter-n" class wouldn't be the right way to go. Instead make a more flexible Functor which goes between arbitrary categories: class (Category c1, Category c2) => Functor c1 c2 f | f -> c1, f -> c2 where fmap :: c1 a b -> c2 (f a) (f b). Then a bifunctor (after uncurrying) is just a functor from the product category. – Gleich

@dfeuer, one example of such work (the only I'm aware of) is Generic Programming with Indexed Functors. If you sacrifice first-orderness they have in the paper, you'll get something quite powerful, but it's not ideal still as you can't e.g. make an index depend on a parameter or define several data types mutually such that they have distinct parameter telescopes. – Halting