Qu'est ce qu'un foncteur contravariant?

du point de vue d'un programmeur, l'essence du fonctionnement est de pouvoir facilement adapter choses. Ce que je veux dire par "s'adapter" ici , c'est que si j'ai un f a et que j'ai besoin d'un f b , j'aimerais un adaptateur qui s'adaptera à mon f a dans mon trou en forme de f b .

il semble intuitif que si je peux transformer un a en un b , que je pourrais être en mesure de transformer un f a en un f b . Et en effet c'est le modèle que la classe Functor de Haskell incarne; si je fournis une fonction a -> b alors fmap me permet d'adapter f a choses en f b choses, sans se soucier de ce que f implique. ¹

bien sûr parlant de types paramétrés comme list-of-x [x] , Maybe y , ou IO z ici, et la chose que nous obtenons à changer avec nos adaptateurs est le x , y , ou z dans les. Si nous voulons la flexibilité pour obtenir un adaptateur de n'importe quelle fonction possible a -> b alors naturellement la chose que nous adaptons doit être également applicable à n'importe quel type possible.

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, seulement ils sont "à l'envers"; pour ceux-ci si nous voulons adapter un f a pour combler un besoin d'un f b nous en fait besoin de fournir une fonction b -> a , pas une fonction a -> b !

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 est parfaitement sensé lorsqu'il est appliqué aux fonctions (et si vous avez fait n'importe quelle programmation substantielle vous avez presque certainement utilisé ces concepts sans connaître la terminologie ou combien largement applicable ils sont), et les deux notions sont si évidemment dual à les uns les autres dans ce contexte.

il est assez bien connu que a -> r est un functor dans r . Cela a du sens; si j'ai un a -> r et que j'ai besoin d'un a -> s , alors je pourrais utiliser une fonction r -> s pour adapter ma fonction originale simplement en post-traitement du résultat. ²

si, d'un autre côté, j'ai une fonction a -> r et ce dont j'ai besoin est un b -> r , alors encore une fois c'est clair que je peux répondre à mon besoin en pré-traitement des arguments avant de les passer à la fonction originale. Mais que dois-je pré-traiter? La fonction originale est une boîte noire; peu importe ce que je fais, il est toujours en attente a entrées. Je dois donc transformer mes valeurs b en valeurs a qu'il attend: mon adaptateur de pré-traitement a besoin d'une fonction b -> a .

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

fait intéressant, la mise en œuvre de la fonction-résultat fmap et la fonction-argument contramap sont presque exactement la même chose: juste la composition de fonction (l'opérateur . )! La seule différence est de quel côté vous composez la fonction adaptateur: ³

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 la deuxième définition de chaque bloc comme la plus perspicace; (covariant) la cartographie sur le résultat d'une fonction est la composition sur la gauche (post-composition si nous voulons prendre une vue "ceci-arrive-après-cela"), alors que la cartographie contravariante de l'argument d'une fonction est la composition sur la droite (pré-composition).

cette intuition généralise assez bien; si une structure f x peut nous donner valeurs de type x (tout comme une fonction a -> r nous donne r valeurs, au moins potentiellement), il pourrait être un covariant Functor dans x , et nous pourrions utiliser une fonction x -> y pour l'adapter en étant un f y . Mais si une f x structure reçoit des valeurs de type x de nous (encore une fois, comme un a -> r argument de la fonction de type a ), alors il pourrait être un Contravariant et nous aurions besoin d'utiliser une y -> x fonction pour l'adapter à être un f y .

je trouve intéressant de réfléchir sur le fait que "les sources sont covariantes, les destinations sont contravariantes". penser du point de vue d'un exécutant de la source/destination plutôt qu'un appelant. Si j'essaie de implémenter un f x qui reçoit des valeurs x je peux" adapter ma propre interface "de sorte que je puisse travailler avec des valeurs y à la place (tout en présentant l'interface "receives x valeurs "à mes appelants) en utilisant une fonction x -> y . En général, nous ne pensons pas de cette façon; même si le implémenter le f x je pense à adapter les choses que j'appelle plutôt que"adapter l'interface de mon interlocuteur à moi". Mais c'est une autre perspective que vous pouvez prendre.

la seule utilisation semi-réelle que j'ai faite de Contravariant (par opposition à l'utilisation implicite de la contre-variabilité des fonctions dans leurs arguments en utilisant la composition-on-the-right, ce qui est très courant) était pour un type Serialiser a qui pourrait sérialiser les valeurs x . Serialiser devait être un Contravariant plutôt qu'un Functor ; étant donné que je peux sérialiser des pieds, je peux aussi sérialiser des barres si je peux Bar -> Foo . ⁴ mais quand on se rend compte que Serialiser a est fondamentalement a -> ByteString cela devient évident; Je ne fais que répéter un cas particulier de l'exemple a -> r .

dans la programmation purement fonctionnelle, il n'y a pas beaucoup d'utilité à avoir quelque chose qui "reçoit des valeurs" sans qu'il donne aussi quelque chose en retour donc tout le les foncteurs contravariants ont tendance à ressembler à des fonctions, mais presque n'importe quelle 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 la raison pour laquelle Functor a volé le bon nom et est utilisé partout (bien, cela et que Functor a été reconnu comme une partie fondamentale de Monad , qui était déjà largement utilisé avant que Functor a été défini comme une classe dans Haskell).

In impératif OO je crois que les foncteurs contravariants peuvent être beaucoup plus communs (mais pas abstraits avec un cadre unifié comme Contravariant ), bien qu'il soit aussi très facile d'avoir la mutabilité et les effets secondaires signifient qu'un type paramétré ne pourrait tout simplement pas être un foncteur du tout (généralement: votre conteneur standard de a qui est à la fois lisible et inscriptible est à la fois un émetteur et un évier de a , et plutôt que de signifier qu'il est à la fois covariant et contravariant il s'avère que signifie qu'il est ni).

---

¹ l'instance Functor de chaque individu f indique comment appliquer des fonctions arbitraires à la forme particulière de ce f , sans se soucier des types particuliers f est appliquée; une belle séparation des préoccupations.

² cette fonction est aussi une monade, équivalente à la Reader ." monade. Je ne vais pas aller au-delà des foncteurs en détail ici, mais étant donné le reste de mon poste une question évidente serait "est le type a -> r aussi une sorte de Monad contravariant dans a alors?". La contre-variabilité ne s'applique pas aux monades malheureusement (voir y a-t-il des monades contre-variables? ), mais il existe un analogue contravariant de Applicative : https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html

³ notez que mon contramap' ici ne correspond pas au contramap réel de Contravariant tel qu'implémenté dans Haskell; vous ne pouvez pas faire a -> r une instance réelle de Contravariant dans le code Haskell simplement parce que le a n'est pas le dernier paramétreur de type de (->) . sur le plan Conceptuel cela fonctionne parfaitement, et vous pouvez toujours utiliser un wrapper newtype pour échanger les paramètres de type et en faire une instance (le contravariant définit le type Op pour exactement ce but).

⁴ au moins pour une définition de "sérialiser" qui n'inclut pas nécessairement la possibilité de reconstruire la barre plus tard, car elle sérialiserait la barre a de manière identique à la Foo à laquelle elle correspond sans aucun moyen d'inclure des informations sur ce qu'était la cartographie.

tout D'abord, une note à propos de notre ami, la classe Functor

Vous pouvez penser à Functor f comme une affirmation que a n'apparaît jamais dans le "négatif". C'est un terme ésotérique pour cette idée: notez que dans les types de données suivants le 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, la 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 pourrait être utile de se rappeler que le troisième exemple est équivalent à data List a = Nil | Cons a (List a) . Dans les callbacks comme a -> List -> r le a apparaît dans le position négative mais le se callback est dans la position négative donc négatif et de multiplier négatif pour être positif.

ce schéma pour signer les paramètres d'une fonction est élaboré dans ce merveilleux billet de blog .

notez maintenant que chacun de ces types admet un Functor . Qui n'est pas une erreur! Les foncteurs sont destinés à modeler l'idée de foncteurs covariants catégoriques, qui " préservent l'ordre des flèches" i.e. f a -> f b par opposition à f b -> f a . Dans Haskell, les types où a n'apparaît jamais dans une position négative admettent toujours Functor . Nous disons que ces types sont covariants sur a .

autrement dit, on pourrait valablement renommer la classe Functor pour Covariant . Ils sont une seule et même idée.

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

Retour à Contravariant

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

• data Void a ( a est fantôme)
• data Unit a = Unit ( a est fantôme de nouveau)
• 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 n'apparaît jamais ou est négatif (dans ces exemples artificiels, a apparaît toujours avant une flèche, ce qui est très simple à déterminer). En conséquence, chacun de ces types admet un instance Contravariant .

un exercice plus intuitif serait de squint à ces types (qui présentent une contre-variation) et puis squint à ces types ci-dessus (qui présentent une covariance) et de voir si vous pouvez intuit une différence dans le sens sémantique de a . Peut-être que c'est utile, ou peut-être que c'est juste encore abscons de la prestidigitation.

quand pourraient - ils être utiles? Par exemple, nous voulons partager une liste de cookies par quel type de puces ils ont. Nous avons un chipEquality :: Chip -> Chip -> Bool . Pour obtenir un Cookie -> Cookie -> Bool , il suffit d'évaluer runEquivalence . contramap cookie2chip . Equivalence $ chipEquality .

jolie verbose! Mais résoudre le problème de la verbosité induite par newtype devra être une autre question...

Autres ressources (ajouter des liens ici que vous les trouverez)

• 24 jours de Hackage: contravariant

• Covariance, la contravariance, et positifs et négatifs des positions

• j'aime profunctors

• Talk: s'Amuser avec Profunctors : je ne saurais trop insister à quel point ce discours est

tout d'abord, la réponse de @haoformayor est excellente, alors considérez cela comme un addendum plutôt qu'une réponse complète.

définition

Un j'aime à penser Foncteur (co/contravariant) est en termes de diagrammes. Cette définition se reflète dans les définitions suivantes. (Je remplace contramap par cmap )

      covariant                           contravariant
f a ─── fmap φ ───▶ f b             g a ◀─── cmap φ ─── g b
 ▲                   ▲               ▲                   ▲
 │                   │               │                   │
 │                   │               │                   │
 a ────── φ ───────▶ b               a ─────── φ ──────▶ b

Note: que le seul changement dans ces deux définitions est la flèche sur le dessus, (bien et les noms pour que je puisse les désigner comme des choses différentes).

exemple

l'exemple que j'ai toujours en tête quand je parle de ces fonctions est - et puis un exemple de f serait type F a = forall r. r -> a (ce qui signifie que le premier argument est arbitraire mais fixe r ), ou en d'autres termes toutes les fonctions avec une entrée commune. Comme toujours l'instance pour (covariant) Functor est juste fmap ψ φ = ψ . φ".

Où le (contravariant) Functor est toutes les fonctions avec un résultat commun - type G a = forall r. a -> r ici l'instance Contravariant serait cmap ψ φ = φ . ψ .

mais qu'est-ce que cela signifie

φ :: a -> b et ψ :: b -> c

habituellement donc (ψ . φ) x = ψ (φ x) ou x ↦ y = φ x et y ↦ ψ y fait sens, ce qui est ommité dans la déclaration pour cmap est que ici

φ :: a -> b mais ψ :: c -> a

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

cela se reflète dans les diagrammes suivants, mais ici nous avons résumé sur l'exemple de fonctions avec source/cible commune - à quelque chose qui a la propriété d'être covariant / contravariant, qui est une chose que vous voyez souvent en mathématiques et/ou 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

Remarque:

en mathématiques, vous avez habituellement besoin d'une loi pour appeler quelque chose functor.

        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 (ψ.φ)

attendu que

cmap φ . cmap ψ = cmap (ψ.φ)