Quels sont les bifoncteurs utilisés pour cela qui ne peuvent être obtenus en composant des foncteurs?

Question

Je suis relativement nouveau à Haskell et j'ai du mal à comprendre l'utilité des bifoncteurs. Je pense que je les comprends en théorie: disons par exemple que si je voulais cartographier un type qui résume plusieurs types concrets, comme Either ou Maybe, il faudrait que je les encapsule dans un bifoncteur. Mais d'une part, ces exemples semblent particulièrement artificiels, et d'autre part, il semble que vous puissiez obtenir la même fonctionnalité simplement à travers la composition. Par exemple, je suis tombé sur ce code dans The Essence of the Iterator Pattern par Jeremy Gibbons et 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 

Je comprends le point est à composer des fonctions de cartographie et de pliage pour créer un motif d'itération et ceci est réalisé par la définition d'un constructeur de données qui a besoin de deux paramètres. Mais en pratique, je ne comprends pas comment cela est différent, en utilisant un foncteur régulier et en composant les fonctions avec fmap au lieu de bimap. Je pense que je dois clairement manquer quelque chose, à la fois avec cet exemple et, probablement, en général.

Answer 1

Je pense que vous y réfléchissez légèrement. Un bifoncteur est juste comme un foncteur à deux paramètres. L'idée de Gibbons et Oliveira n'est qu'une application des bifoncteurs, tout comme le zoo standard des systèmes de récursion n'est qu'une application des foncteurs.

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

Bifunctor s ont une sorte de * -> * -> * et les deux paramètres peuvent être mis en correspondance sur covariante. Comparez ceci aux Functor s, qui n'ont qu'un seul paramètre (f :: * -> *) qui peut être mappé de manière covariante. Par exemple, pensez à l'instance Functor habituelle de Either. Il ne vous permet que de fmap sur le second paramètre de type - Right valeurs sont mappées, Left valeurs restent telles quelles.

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

Cependant, son instance Bifunctor vous permet de cartographier les deux moitiés de la somme.

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

De même pour tuples: Functor exemple de (,) vous permet de cartographier la deuxième composante, mais Bifunctor vous permet de cartographier les deux parties.

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

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

Notez que Maybe, que vous avez mentionné, ne rentre pas dans le cadre de bifoncteurs parce qu'il n'a qu'un seul paramètre.

---

Sur la question de Fix, le point fixe d'un bifoncteur vous permet de caractériser les types récursifs qui ont un paramètre de type fonctorielle, comme la plupart des structures de type conteneur. Utilisons les listes comme exemple.

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

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

En utilisant la norme fonctorielle Fix, comme je l'ai ci-dessus, il n'y a pas de dérivation générique d'une instance de Functor pour List, parce Fix ne sait rien au sujet de paramètre d » Lista. C'est, je ne peux pas écrire quelque chose comme instance Something f => Functor (Fix f) parce que Fix a le mauvais type.Je dois tourner la manivelle à la main un map pour les listes, en utilisant peut-être 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 

La version bifunctorial de Fix ne permet une instance de Functor. Fix utilise l'un des paramètres du bifoncteur pour brancher l'occurrence récursive de Fix f a et l'autre pour représenter le paramètre fonctorial du type de données résultant.

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 

Nous pouvons écrire:

deriveBifunctor ''ListF 

type List = Fix ListF 

et obtenir l'instance Functor gratuitement:

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

Bien sûr, si vous voulez travailler génériquement avec des structures récursives avec plus d'un paramètre alors vous devez généraliser à tri-functors, quad-foncteurs, etc ... Ceci est clairement pas durable, et beaucoup de travail (dans des langages de programmation plus avancés) a été mis dans la conception mo des systèmes flexibles pour caractériser les types.