Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What are bifunctors?

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.

like image 620
Sophia Gold Avatar asked Dec 10 '16 09:12

Sophia Gold


1 Answers

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.

like image 132
Benjamin Hodgson Avatar answered Oct 23 '22 21:10

Benjamin Hodgson