Qu'est-ce qu'un foncteur contravariant ?

Question

Le type me sidère :

class Contravariant (f :: * -> *) where
  contramap :: (a -> b) -> f b -> f a

Puis j'ai lu ce mais contrairement au titre, je n'ai pas été plus éclairé.

Quelqu'un peut-il expliquer ce qu'est un foncteur contravariant et donner quelques exemples ?

Answer 1

Du point de vue d'un programmeur, l'essence de la notion de foncteur est de pouvoir facilement adapter choses. Ce que j'entends par "adapter" ici, c'est que si j'ai une f a et j'ai besoin d'un f b Je voudrais un adaptateur qui s'adapterait à mon f a dans mon f b -trou en forme d'étoile.

Il semble intuitif que si je peux transformer un a en un b que je puisse être capable de transformer un f a dans un f b . Et en effet, c'est le modèle que le langage Haskell Functor si je fournis une classe a -> b fonction alors fmap me permet de m'adapter f a des choses dans f b les choses, sans se soucier de ce que f implique. 1

Bien sûr, en parlant de types paramétrés comme list-of-x [x] , Maybe y ou IO z ici, et ce que nous pouvons changer avec nos adaptateurs, c'est le x , y ou z dans celles-ci. Si nous voulons avoir la flexibilité d'obtenir un adaptateur de n'importe quelle fonction possible a -> b alors bien sûr, la chose que nous adaptons doit être également applicable à tous les types possibles.

Ce qui est moins intuitif (au début), c'est qu'il y a des types qui peuvent être adaptés presque exactement de la même manière que les types fonctionnels, sauf qu'ils sont "à l'envers" ; pour ceux-ci, si nous voulons adapter un type f a pour répondre au besoin d'un f b nous devons en fait fournir un b -> a et non une fonction a -> b un !

Mon exemple concret préféré est en fait le type de fonction a -> r (a pour argument, r pour résultat) ; tout ce non-sens abstrait prend tout son sens lorsqu'il est appliqué aux fonctions (et si vous avez fait un peu de programmation, vous avez certainement utilisé ces concepts sans en connaître la terminologie ou sans savoir à quel point ils sont largement appliqués), et les deux notions sont si manifestement duales l'une de l'autre dans ce contexte.

Il est assez bien connu que a -> r est un foncteur dans r . Cela a du sens ; si j'ai un a -> r et j'ai besoin d'un a -> s alors je pourrais utiliser un r -> s pour adapter ma fonction originale en post-traitant simplement le résultat. 2

Si, d'un autre côté, j'ai une a -> r et ce dont j'ai besoin est une fonction b -> r Mais là encore, il est clair que je peux répondre à mon besoin en prétraitant les arguments avant de les transmettre à la fonction originale. Mais avec quoi dois-je les prétraiter ? La fonction d'origine est une boîte noire ; quoi que je fasse, elle s'attend toujours à ce que a entrées. Donc je dois tourner mon b dans le a qu'il attend : mon adaptateur de prétraitement a besoin d'une valeur de b -> a fonction.

Ce que nous venons de voir, c'est que le type de fonction a -> r est un covariant dans r et un contravariant dans a . Je pense que cela signifie que nous pouvons adapter le résultat d'une fonction, et que le type de résultat "change avec" l'adaptateur. r -> s alors que lorsque nous adaptons l'argument d'une fonction, le type de l'argument change "dans la direction opposée" à l'adaptateur.

Il est intéressant de noter que l'implémentation de la fonction-résultat fmap et l'argument-fonction contramap sont presque exactement la même chose : juste la composition de fonctions (le . opérateur) ! La seule différence est de savoir de quel côté vous composez la fonction adaptateur : 3

fmap :: (r -> s) -> (a -> r) -> (a -> s)
fmap adaptor f = adaptor . f
fmap adaptor = (adaptor .)
fmap = (.)

contramap' :: (b -> a) -> (a -> r) -> (b -> r)
contramap' adaptor f = f . adaptor
contramap' adaptor = (. adaptor)
contramap' = flip (.)

Je considère que la deuxième définition de chaque bloc est la plus perspicace ; le mappage (covariant) sur le résultat d'une fonction est une composition à gauche (post-composition si nous voulons adopter un point de vue "this-happens-after-that"), tandis que le mappage contravariant sur l'argument d'une fonction est une composition à droite (pré-composition).

Cette intuition se généralise assez bien ; si une f x structure peut donnez-nous valeurs de type x (tout comme un a -> r nous donne r du moins potentiellement), il pourrait s'agir d'une valeur covariante. Functor en x et nous pourrions utiliser un x -> y pour l'adapter en tant que fonction f y . Mais si un f x structure reçoit valeurs de type x de nous (encore une fois, comme un a -> r l'argument de la fonction de type a ), alors il pourrait s'agir d'un Contravariant et nous devrions utiliser un foncteur y -> x pour l'adapter à la fonction f y .

Je trouve intéressant de réfléchir au fait que cette intuition "les sources sont covariantes, les destinations sont contravariantes" s'inverse lorsque l'on se place du point de vue d'une exécutant de la source/destination plutôt qu'un appelant. Si j'essaie de mettre en œuvre un f x qui reçoit x valeurs que je peux "adapter ma propre interface" afin de pouvoir travailler avec y à la place (tout en présentant toujours le message "reçoit x valeurs " à mes interlocuteurs) en utilisant une interface x -> y fonction. Habituellement, nous ne pensons pas de cette manière ; même en tant qu'implémenteur de la fonction f x Je pense à adapter les choses que j'appelle plutôt qu'à "adapter l'interface de mon appelant à moi". Mais c'est une autre perspective que vous pouvez adopter.

La seule utilisation dans le monde semi-réel que j'ai fait de Contravariant (par opposition à l'utilisation implicite de la contravariance des fonctions dans leurs arguments en utilisant la composition à droite, ce qui est très courant) était pour un type Serialiser a qui pourrait sérialiser x valeurs. Serialiser devait être un Contravariant plutôt qu'un Functor ; étant donné que je peux sérialiser les Foos, je peux aussi sérialiser les Bars si je peux Bar -> Foo . 4 Mais quand vous réalisez que Serialiser a est en fait a -> ByteString cela devient évident ; je ne fais que répéter un cas particulier de l'approche de la a -> r exemple.

Dans la programmation fonctionnelle pure, il n'est pas très utile d'avoir quelque chose qui "reçoit des valeurs" sans qu'il ne donne également quelque chose en retour, de sorte que tous les foncteurs contravariants ont tendance à ressembler à des fonctions, mais presque toute structure de données simple qui peut contenir des valeurs d'un type arbitraire sera un foncteur covariant dans ce paramètre de type. C'est pourquoi Functor a volé le bon nom très tôt et est utilisé partout (enfin, cela et cela Functor a été reconnu comme un élément fondamental de la Monad qui était déjà largement utilisé avant Functor a été défini comme une classe en Haskell).

Dans le domaine de l'OO impératif, je pense que les foncteurs contravariants sont beaucoup plus courants (mais ils ne sont pas abstraits dans un cadre unifié comme celui de l'OO impératif). Contravariant ), bien qu'il soit également très facile de faire en sorte que la mutabilité et les effets secondaires signifient qu'un type paramétré ne peut tout simplement pas être un foncteur (communément : votre conteneur standard de a qui est à la fois lisible et inscriptible est à la fois un émetteur et un récepteur de a et plutôt que de signifier qu'il est à la fois covariant et contravariant, il s'avère que cela signifie qu'il n'est ni l'un ni l'autre).

---

1 Le site Functor instance de chaque individu f dit comment appliquer des fonctions arbitraires à la forme particulière de cette f sans se soucier des types particuliers f est appliqué ; une belle séparation des préoccupations.

2 Ce foncteur est également une monade, équivalente à la fonction Reader monad. Je ne vais pas m'étendre sur les foncteurs en détail ici, mais étant donné le reste de mon post, une question évidente serait "est-ce que le a -> r type également une sorte de monade contravariante en a alors ?". Malheureusement, la contravariance ne s'applique pas aux monades (cf. Existe-t-il des monades contravariantes ? ), mais il existe un analogue contravariant de Applicative : https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html

3 Notez que mon contramap' ici ne correspond pas à l'actuel contramap de Contravariant telle qu'elle est implémentée en Haskell ; vous ne pouvez pas faire de la a -> r une instance réelle de Contravariant dans le code Haskell simplement parce que le a n'est pas le dernier paramètre de type de (->) . Conceptuellement cela fonctionne parfaitement bien, et vous pouvez toujours utiliser un wrapper newtype pour échanger les paramètres du type et en faire une instance (le contravariant définit le type Op dans ce but précis).

4 Au moins pour une définition de "sérialiser" qui n'inclut pas nécessairement la possibilité de reconstruire la barre plus tard, puisque cela sérialiserait la barre à l'identique du Foo auquel elle correspond, sans possibilité d'inclure une quelconque information sur la nature de la correspondance.

Answer 2

Tout d'abord, la réponse de @haoformayor est excellente, alors considérez ceci plus comme un addendum que comme une réponse complète.

Définition

L'une des façons dont j'aime penser aux foncteurs (co/contravariants) est en termes de diagrammes. La définition est reflétée dans les suivants. (J'abrège contramap con cmap )

      covariant                           contravariant
f a  fmap   f b             g a  cmap   g b

 a    b               a    b

Notez que le seul changement dans ces deux définitions est la flèche sur le dessus, (ainsi que les noms pour que je puisse m'y référer comme à des choses différentes).

Exemple

L'exemple que j'ai toujours en tête lorsque je parle de ceux-ci est celui des fonctions - et ensuite un exemple de f serait type F a = forall r. r -> a (ce qui signifie que le premier argument est arbitraire mais fixé r ), ou en d'autres termes toutes les fonctions ayant une entrée commune. Comme toujours, l'instance pour les fonctions (covariantes) Functor est juste fmap \= . `.

Où le (contravariant) Functor est l'ensemble des fonctions ayant un résultat commun - type G a = forall r. a -> r ici le Contravariant L'exemple serait cmap = . .

Mais qu'est-ce que ça veut dire

:: a -> b y :: b -> c

généralement donc ( . ) x = ( x) o x y = x y y y a du sens, ce qui est omis dans la déclaration de cmap c'est qu'ici

:: a -> b mais :: **c -> a**

donc ne peut pas prendre le résultat de mais il peut transformer ses arguments en quelque chose peut utiliser - donc x y = x y y y est le seul choix correct.

Cela se reflète dans les diagrammes suivants, mais ici nous avons fait abstraction de l'exemple des fonctions avec une source/cible commune - à quelque chose qui a la propriété d'être covariant/contravariant, ce qui est une chose que vous voyez souvent en mathématiques et/ou en haskell.

                 covariant
f a  fmap   f b  fmap   f c

 a    b    c

               contravariant
g a  cmap   g b  cmap   g c

 a    b    c

Remarques :

En mathématiques, on a généralement besoin d'une loi pour appeler quelque chose un foncteur.

        covariant
   a                        f a

     .      fmap        fmap (.)

  b  c                f b  f c
                           fmap 

       contravariant
   a                        f a

     .      cmap        cmap (.)

  b  c                f b  f c
                           cmap 

ce qui revient à dire

fmap  . fmap  = fmap (.)

alors que

cmap  . cmap  = cmap (.)

Answer 3

Tout d'abord, une note sur notre ami, la classe Functor.

Vous pouvez penser à Functor f comme une affirmation selon laquelle a n'apparaît jamais dans la "position négative". Il s'agit d'un terme ésotérique pour cette idée : Remarquez que, dans les types de données suivants, l'élément a semble agir comme une variable "résultat".

• newtype IO a = IO (World -> (World, a))

• newtype Identity a = Identity a

• newtype List a = List (forall r. r -> (a -> List a -> r) -> r)

Dans chacun de ces exemples a apparaît dans une position positive. Dans un certain sens, le a pour chaque type représente le "résultat" d'une fonction. Il peut être utile de penser à a dans le deuxième exemple comme () -> a . Et il peut être utile de se rappeler que le troisième exemple est équivalent à data List a = Nil | Cons a (List a) . Dans les rappels comme a -> List -> r el a apparaît en position négative mais le le rappel lui-même est en position négative, donc négatif et négatif se multiplient pour devenir positif.

Ce schéma de signature des paramètres d'une fonction est le suivant élaboré dans ce merveilleux blog post .

Notez maintenant que chacun de ces types admet un Functor . Ce n'est pas une erreur ! Les foncteurs sont censés modéliser l'idée de foncteurs catégoriques covariants, qui "préservent l'ordre des flèches", à savoir f a -> f b à l'opposé de f b -> f a . En Haskell, les types où a n'apparaît jamais dans une position négative admet toujours Functor . Nous disons que ces types sont covariants sur a .

En d'autres termes, on pourrait valablement renommer le fichier Functor la classe à être Covariant . Il s'agit d'une seule et même idée.

La raison pour laquelle cette idée est formulée si bizarrement avec le mot "jamais" est que a peut apparaître à la fois dans un emplacement positif et négatif, dans ce cas nous disons que le type est invariant sur a . a peut aussi ne jamais apparaître (comme un type fantôme), dans ce cas nous disons que le type est à la fois covariant et contravariant sur a - bivariant.

Retour à Contravariant

Ainsi, pour les types où a n'apparaît jamais en position positive, nous disons que le type est contravariant en a . Chacun de ces types Foo a admettra un instance Contravariant Foo . Voici quelques exemples, tirés du contravariant paquet :

• data Void a ( a est fantôme)
• data Unit a = Unit ( a est à nouveau fantôme)
• newtype Const constant a = Const constant
• newtype WriteOnlyStateVariable a = WriteOnlyStateVariable (a -> IO ())
• newtype Predicate a = Predicate (a -> Bool)
• newtype Equivalence a = Equivalence (a -> a -> Bool)

Dans ces exemples a est soit bivariant, soit simplement contravariant. a soit n'apparaît jamais, soit est négative (dans ces exemples inventés a apparaît toujours avant une flèche, ce qui rend sa détermination très simple). Par conséquent, chacun de ces types admet une fonction instance Contravariant .

Un exercice plus intuitif serait de loucher sur ces types (qui présentent une contravariance) puis sur les types ci-dessus (qui présentent une covariance) et de voir si vous pouvez intuitionner une différence dans la signification sémantique de a . Peut-être cela est-il utile, ou peut-être s'agit-il encore d'un tour de passe-passe abscons.

Quand pourraient-ils être utiles en pratique ? Par exemple, nous voulons partitionner une liste de cookies en fonction du type de chips qu'ils contiennent. Nous avons un chipEquality :: Chip -> Chip -> Bool . Pour obtenir un Cookie -> Cookie -> Bool nous évaluons simplement runEquivalence . contramap cookie2chip . Equivalence $ chipEquality .

Plutôt verbeux ! Mais la résolution du problème de la verbosité induite par les nouveaux types devra faire l'objet d'une autre question...

Autres ressources (ajoutez les liens ici au fur et à mesure que vous les trouvez)

• 24 jours de piratage : contravariant

• Covariance, contravariance et positions positives et négatives

• J'aime les professeurs

• Parler : S'amuser avec les Profuncteurs : Je ne saurais trop insister sur l'importance de cette conférence.

Answer 4

Je sais que cette réponse ne sera pas aussi académique que les autres, mais elle est simplement basée sur les implémentations courantes de la contravariante que vous rencontrerez.

Tout d'abord, un conseil : ne lisez pas les contraMap type de fonction en utilisant la même métaphore mentale pour f comme vous le faites lorsque vous lisez le bon vieux Functor's map .

Tu sais comment tu penses :

"une chose qui contient (ou produit ) et t "

...quand vous lisez un type comme f t ?

Eh bien, vous devez arrêter de faire ça, dans ce cas.

Le foncteur contravariant est "le dual" du foncteur classique, donc, lorsque vous voyez f a en contraMap vous devriez penser à la métaphore "double" :

f t est une chose qui CONSOMME a t

Maintenant contraMap devrait commencer à avoir un sens :

contraMap :: (a -> b) -> f b ...

...pause juste là, et le type est parfaitement raisonnable :

1. Une fonction qui "produit" un b .
2. Une chose qui "consomme" une b .

Le premier argument cuisine le b . Le deuxième argument mange le b .

C'est logique, non ?

Maintenant, finissez d'écrire le type :

contraMap :: (a -> b) -> f b -> f a

Donc, à la fin, cette chose doit donner un " consommateur de a ".

Eh bien, nous pouvons sûrement construire cela, étant donné que notre premier argument est une fonction qui prend un a comme entrée.

Une fonction (a -> b) devrait constituer un bon élément de base pour la construction d'un "consommateur de". a ".

Alors contraMap vous permet de créer un nouveau "consommateur", comme celui-ci (attention : symboles inventés à l'arrivée) :

(takes a as input / produces b as output) ~~> (consumer of b)

• A gauche de mon symbole inventé : Le premier argument de contraMap (c'est-à-dire (a -> b) ).
• A droite : Le deuxième argument (c'est-à-dire f b ).
• Le tout collé ensemble : Le résultat final de contraMap (une chose qui sait comment consommer un a c'est-à-dire f a ).

Answer 5

Un autre point de vue sur le sujet, limité à fonctions vus comme des foncteurs contravariants. (Voir aussi ce .)

Fonctions comme conteneurs (donc Functor s ) de leur résultat

Une fonction f de type a -> b peut être considéré comme contenant une valeur de type b à laquelle nous avons accès lorsque nous introduisons une valeur de type a à f .

Maintenant, les choses qui sont des conteneurs d'autres choses peuvent être faites Functor dans le sens où nous pouvons appliquer une fonction g à leur contenu, en appliquant fmap g au foncteur lui-même.

Par conséquent, f qui est de type a -> b peut être vu comme un foncteur dans b c'est-à-dire (->) a peut devenir un Functor . Pour ce faire, nous devons définir fmap : fmap ping une fonction g sur le "contenu" de f signifie essentiellement l'application g sur tout ce qui f retourne (une fois qu'il a été alimenté avec une entrée de type a évidemment), ce qui signifie que fmap g f = \x -> g (f x) ou, de manière plus concise, fmap g f = g . f .

fmap ping sur a -> b fonctions \= post-traitement leur résultat de type b

En guise de dernière réflexion : une fonction de type a -> b est un foncteur dans b parce que nous pouvons poste -le traiter à l'aide d'une fonction b -> c (où c est juste un autre type).

contramap ping sur a -> b fonctions \= prétraitement une entrée pour obtenir a

Mais que faire si nous voulons utiliser une fonction g (de type c -> a ) à pré -Traiter une valeur d'un certain type c pour obtenir la valeur de type a que nous voulons alimenter à f ?

Eh bien, il est clair que dans ce cas, nous voulons g d'agir avant f c'est-à-dire que nous recherchons f . g .

Et nous voulons f . g pour être la "mise en œuvre" du concept de " cartographie g en f " . En d'autres termes, nous voulons whichmap g f = f . g .

Devinez quoi ? whichmap est en fait l'implémentation de contramap pour les fonctions ! Et contramap est ce que vous devez implémenter pour faire d'un type une instance de la classe Contravariant foncteur de typeclasse.

Eh bien, pas vraiment. (-> b) ...

En fait, il n'y a pas vraiment de instance de Contravariant miroir instance Functor ((->) r) Je crois que ce n'est pas parce que instance Contravariant (-> r) / instance Contravariant (flip (->) r) sont des syntaxes invalides ; un autre type est donc créé, via

newtype Op a b = Op { getOp :: b -> a }

y ce est transformé en une instance de Contravariant :

instance Contravariant (Op a) where
  contramap f g = Op (getOp g . f)

Les deux derniers morceaux de code sont tirés de hackage .

L'exemple en haut de la page ce La page est également très éclairante.