What bifunctors used for this cannot be achieved by compiling functors?

Question

I am relatively new to Haskell and have difficulty understanding the usefulness of bifuntors. I think I understand them in theory: say, for example, if I wanted to map a type that abstracts a few specific types, such as Either or Maybe I will need to encapsulate them in a bifunter. But, on the one hand, these examples seem especially far-fetched, and on the other hand, it seems that you can achieve the 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 S. d. S. Oliveira:

import Data.Bifunctor data Fix sa = In {out::sa (Fix sa) } map' :: Bifunctor s => (a -> b) -> Fix sa -> Fix sb map' f = In . bimap f (map' f) . out fold' :: Bifunctor s => (sab -> b) -> Fix sa -> b fold' f = f . bimap id (fold' f) . out unfold' :: Bifunctor s => (b -> sab) -> b -> Fix sa unfold' f = In . bimap id (unfold' f) . f 

I understand that you need to create display and collapse functions to create an iterator template, and this is achieved by defining a data constructor that requires two parameters. But in practice, I don’t understand how this is different than using a regular functor and compiling functions using fmap instead of bimap. I think that I, obviously, should miss something, both with this example, and, most likely, as a whole.

Answer 1

I think you thought about it a bit. A bifuntor is similar to a two-parameter functor. The idea of ​​Gibbons and Oliveira is just one use of bifuntors, just like the standard zoo of recursive schemes is just one use of functors.

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

Bifunctor have the form * -> * -> * , and both parameters can be covariantly displayed. Compare this to the usual Functor s, which has only one parameter ( f :: * -> * ), which can be covariantly displayed.

For example, think of the Either regular Functor instance. It allows only fmap on the second parameter of the type - Right to receive values, Left values ​​remain as they are.

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

However, its instance of Bifunctor allows Bifunctor to compare both halves of the amount.

 instance Bifunctor Either where bimap fg (Left x) = Left (fx) bimap fg (Right y) = Right (gy) 

Similarly for tuples: an instance (,) Functor allows you to display only the second component, but Bifunctor allows Bifunctor to display both parts.

 instance Functor ((,) a) where fmap f (x, y) = (x, fy) instance Bifunctor (,) where bimap fg (x, y) = (fx, gy) 

Note that Maybe , which you mentioned, does not fit into the structure of the bunkers, since it has only one parameter.

---

In the Fix question, a fixed bifunter point allows us to characterize recursive types that have a functorial type parameter, such as most container structures. Lists can be used as an example.

 newtype Fix f = Fix { unFix :: f (Fix f) } data ListF ar = Nil_ | Cons_ ar deriving Functor type List a = Fix (ListF a) 

Using the standard functorial Fix , as I said above, there is no general output from the Functor instance for List , since Fix knows nothing about the List a parameter. That is, I cannot write something like instance Something f => Functor (Fix f) , because Fix has the wrong look. I need to scroll the map list for lists, possibly using cata :

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

The bifuntorial version of Fix allows an instance of Functor . Fix uses one of the bifurcator parameters to insert the recursive appearance of Fix fa , and the other for the resulting functional parameter of the data type.

 newtype Fix fa = Fix { unFix :: fa (Fix fa) } 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 a copy of Functor for free:

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

Of course, if you want to work with recursive structures with several parameters as a whole, you need to generalize to three-functors, quad-functors, etc. This is clearly not stable and a lot of work (in more advanced programming languages) was introduced into the development of more flexible systems for characterizing types.