Confus par la signification de la classe de type ‘Alternative’ et sa relation avec d’autres classes de type

Je suis passé par le Typeclassopedia pour apprendre les classes de types. Je suis coincé à comprendre Alternative (et MonadPlus , d’ailleurs).

Les problèmes que j’ai:

  • la ‘pedia dit que “la classe de type alternative est pour les foncteurs applicatifs qui ont aussi une structure monoïde.” Je ne comprends pas – Alternative ne signifie-t-il pas quelque chose de totalement différent du Monoïde? c’est-à-dire que j’ai compris que le sharepoint la classe de type Alternative était de choisir entre deux choses, alors que je pensais que les Monoïdes consistaient à combiner des choses.

  • Pourquoi Alternative a-t-il besoin d’une méthode / d’un membre empty ? Je peux me tromper, mais il ne semble pas être utilisé du tout … du moins dans le code que je pourrais trouver. Et cela ne semble pas correspondre au thème de la classe – si j’ai deux choses et que je dois en choisir une, à quoi ai-je besoin d’un «vide»?

  • Pourquoi la classe de type Alternative a-t-elle besoin d’une contrainte Applicative, et pourquoi a-t-elle besoin d’une sorte de * -> * ? Pourquoi ne pas simplement avoir :: a -> a -> a ? Toutes les instances peuvent encore être implémentées de la même manière … Je pense (pas sûr). Quelle valeur apporte-t-il à Monoid?

  • quel est le but de la classe de type MonadPlus ? Est-ce que je ne peux pas débloquer toute sa bonté en utilisant simplement quelque chose comme une Monad et une Alternative ? Pourquoi ne pas simplement le laisser tomber? (Je suis sûr que je me trompe, mais je n’ai pas de contre-exemples)

J’espère que toutes ces questions sont cohérentes …!


Mise à jour de Bounty: la réponse de @ Antal est un bon début, mais le troisième sortingmestre est toujours ouvert: qu’est-ce qu’Alternative ne fournit pas? Je trouve cette réponse insatisfaisante car elle manque d’exemples concrets et d’une discussion spécifique sur la manière dont la bienveillance de l’alternative le distingue du monoïde.

Si c’est pour combiner les effets applicatifs avec le comportement de Monoid, pourquoi pas juste:

 liftA2 mappend 

Cela est encore plus déroutant pour moi car de nombreuses instances Monoid sont exactement les mêmes que les instances Alternative.

C’est pourquoi je cherche des exemples spécifiques qui montrent pourquoi Alternative est nécessaire, et comment c’est différent – ou signifie quelque chose de différent – de Monoid.

Pour commencer, permettez-moi de répondre brièvement à chacune de ces questions. Je développerai ensuite chacune d’elles en une réponse plus détaillée, mais nous espérons que celles-ci vous aideront à naviguer dans ces réponses.

  1. Non, Alternative et Monoid ne signifient pas des choses différentes; Alternative est pour les types qui ont la structure à la fois de Applicative et de Monoid . «Choisir» et «combiner» sont deux intuitions différentes pour un même concept plus large.

  2. Alternative contient empty aussi bien que <|> car les concepteurs ont pensé que cela serait utile, et parce que cela donne lieu à un monoïde. En termes de prélèvement, le empty correspond à un choix impossible.

  3. Nous avons besoin à la fois d’ Alternative et de Monoid car le premier obéit (ou devrait) plus de lois que le second; ces lois concernent la structure monoïdale et applicative du type constructeur. De plus, Alternative ne peut pas dépendre du type interne, alors que Monoid peut le faire.

  4. MonadPlus est légèrement plus fort MonadPlus , car il doit obéir à plus de lois; ces lois relient la structure monoïdale à la structure monadique en plus de la structure applicative. Si vous avez des exemples des deux, ils doivent coïncider.


Est-ce que Alternative ne signifie pas quelque chose de totalement différent du Monoid ?

Pas vraiment! Une partie de la raison de votre confusion est que la classe Haskell Monoid utilise des noms assez mauvais (enfin, insuffisamment généraux). Voici comment un mathématicien définirait un monoïde (étant très explicite à ce sujet):

Définition. Un monoïde est un ensemble M doté d’un élément distingué εM et d’un opérateur binary ·: M × MM , noté par juxtaposition, de sorte que les deux conditions suivantes sont réunies:

  1. ε est l’identité: pour tout mM , m ε = ε m = m .
  2. · Est associatif: pour tout m ₁, m ₂, mM , ( mm ₂) m ₃ = m ₁ (m₂ m ₃).

C’est tout. Dans Haskell, ε est orthographié comme mempty et · est orthographié mappend (ou, ces jours-ci, <> ), et l’ensemble M est le type M par instance Monoid M where ...

En regardant cette définition, nous voyons que cela ne dit rien sur «combiner» (ou sur «choisir», d’ailleurs). Il dit des choses sur et à propos de ε , mais c’est tout. Maintenant, il est certainement vrai que combiner les choses fonctionne bien avec cette structure: ε correspond à ne pas avoir de choses, et mm ₂ dit que si je regarde les choses ensemble, je peux avoir une nouvelle chose contenant toutes leurs choses. Mais voici une intuition alternative: ε ne correspond à aucun choix, et mm ₂ correspond à un choix entre m ₁ et m ₂. Ceci est l’intuition «picking». Notez que les deux obéissent aux lois du monoïde:

  1. Ne rien avoir du tout et n’avoir pas le choix sont à la fois l’identité.
    • Si je n’ai pas de truc et que je le regarde avec des trucs, je me retrouve avec les mêmes choses.
    • Si j’ai le choix entre aucun choix (quelque chose d’impossible) et un autre choix, je dois choisir l’autre (possible) choix.
  2. Glomming collections ensemble et faire un choix sont tous deux associatifs.
    • Si j’ai trois collections de choses, peu importe si je regarde les deux premières ensemble, puis la troisième, ou les deux dernières ensemble, puis la première; Quoi qu’il en soit, je me retrouve avec la même collection glommed totale.
    • Si j’ai le choix entre trois choses, peu importe que je (a) choisisse d’abord entre la première ou la deuxième et la troisième, puis, si nécessaire, entre la première et la deuxième, ou et deuxième ou troisième et, si nécessaire, entre le deuxième et le troisième. De toute façon, je peux choisir ce que je veux.

(Note: je joue vite et en vrac ici, c’est pourquoi c’est de l’intuition. Par exemple, il est important de se rappeler que · il n’est pas nécessaire d’être commutatif, ce qui est plus clair: il est parfaitement possible que mmmm ₁ .)

Voici: ces deux sortes de choses (et bien d’autres – multiplier les nombres, soit les combiner, soit les choisir), obéissent aux mêmes règles. Avoir une intuition est important pour développer la compréhension, mais ce sont les règles et les définitions qui déterminent ce qui se passe réellement .

Et la meilleure partie est que ces deux intuitions peuvent être interprétées par le même transporteur! Soit M un ensemble d’ensembles (pas un ensemble de tous les ensembles!) Contenant l’ensemble vide, soit ε l’ensemble vide ∅, et laissez · s’unir ∪. Il est facile de voir que ∅ est une identité pour ∪, et que ∪ est associatif, nous pouvons donc conclure que ( M , ∅, ∪) est un monoïde. À présent:

  1. Si nous pensons aux ensembles comme étant des ensembles de choses, alors ∪ correspond à les rassembler pour obtenir plus de choses – l’intuition «combinée».
  2. Si nous pensons aux ensembles comme représentant des actions possibles, alors ∪ correspond à l’augmentation de votre pool d’actions possibles parmi lesquelles choisir – l’intuition de «sélection».

Et c’est exactement ce qui se passe avec [] dans Haskell: [a] est un Monoid pour tous les a et [] tant que foncteur applicatif (et monad) est utilisé pour représenter le non-déterminisme. Les intuitions de combinaison et de sélection coïncident toutes deux au même type: mempty = empty = [] et mappend = (<|>) = (++) .

Donc, la classe Alternative est juste là pour représenter les objects qui (a) sont des foncteurs applicatifs, et (b) lorsqu’ils sont instanciés à un type, ils ont une valeur et une fonction binary qui suivent certaines règles. Quelles règles? Les règles du monoïde. Pourquoi? Parce que ça s’avère utile 🙂


Pourquoi Alternative t-il besoin d’une méthode / d’un membre vide?

Eh bien, la réponse sarcastique est «parce que Alternative représente une structure monoïde». Mais la vraie question est: pourquoi une structure monoïde? Pourquoi pas un semigroupe, un monoïde sans ε ? Une réponse consiste à affirmer que les monoides sont simplement plus utiles. Je pense que beaucoup de gens (mais peut – être pas Edward Kmett ) seraient d’accord avec cela; presque tout le temps, si vous avez un bon sens (<|>) / mappend / ·, vous pourrez définir un sens empty / mempty / ε . D’un autre côté, avoir la généralité supplémentaire est bien, car il vous permet de placer plus de choses sous le parapluie.

Vous voulez aussi savoir comment cela se mêle à l’intuition «picking». Gardant à l’esprit que, dans un certain sens, la bonne réponse est «savoir à quel moment abandonner l’intuition», je pense que vous pouvez unifier les deux. Considérons [] , le foncteur applicatif pour le non-déterminisme. Si je combine deux valeurs de type [a] avec (<|>) , cela correspond à une sélection non déterministe d’une action de gauche ou d’une action de la droite. Mais parfois, vous n’aurez aucune action possible d’un côté et c’est bien. De même, si l’on considère les parsingurs, (<|>) représente un parsingur qui parsing soit ce qui est à gauche, soit ce qui est à droite (il sélectionne). Et si vous avez un parsingur qui échoue toujours, cela finit par être une identité: si vous le choisissez, vous le rejetez immédiatement et essayez l’autre.

Tout cela dit, rappelez-vous qu’il serait tout à fait possible d’avoir une classe presque comme Alternative , mais manquant de empty . Ce serait parfaitement valable – ce pourrait même être une super-classe d’ Alternative – mais ce n’est pas ce que Haskell a fait. Vraisemblablement, cela est imprévisible quant à ce qui est utile.


Pourquoi la classe de type Alternative t-elle besoin d’une contrainte Applicative et pourquoi a-t-elle besoin d’une sorte de * -> * ? … Pourquoi ne pas utiliser [ liftA2 mappend ]

Eh bien, considérons chacun de ces trois changements proposés: se débarrasser de la contrainte Applicative pour Alternative ; changer le genre d’argument de Alternative ; et en utilisant liftA2 mappend au lieu de <|> et pure mempty au lieu de empty . Nous allons d’abord regarder ce troisième changement, puisqu’il est le plus différent. Supposons que nous ayons complètement supprimé Alternative et remplacé la classe par deux fonctions simples:

 fempty :: (Applicative f, Monoid a) => fa fempty = pure mempty (>|<) :: (Applicative f, Monoid a) => fa -> fa -> fa (>|<) = liftA2 mappend 

Nous pourrions même garder les définitions de some et de many . Et cela nous donne une structure monoïde, c'est vrai. Mais il semble que cela nous donne le mauvais. Devrait Just fst >|< Just snd échouer, puisque (a,a) -> a n'est pas une instance de Monoid ? Non, mais c'est ce que le code ci-dessus produirait. L'instance monoïde que nous voulons est celle qui est agnostique de type interne (pour reprendre la terminologie de Matthew Farkas-Dyck dans une discussion haskell-café très similaire qui pose des questions très similaires); Alternative structure Alternative est un monoïde déterminé par la structure de f , pas la structure de l'argument de f .

Maintenant que nous pensons que nous voulons laisser Alternative comme une sorte de classe de type, regardons les deux manières proposées de le changer. Si nous changeons le genre, nous devons nous débarrasser de la contrainte Applicative ; Applicative ne parle que des choses du genre * -> * , et il est donc impossible de s'y référer. Cela laisse deux changements possibles; le premier changement, plus mineur, consiste à se débarrasser de la contrainte Applicative mais à laisser le type seul:

 class Alternative' f where empty' :: fa (<||>) :: fa -> fa -> fa 

L'autre changement, plus important, consiste à se débarrasser de la contrainte Applicative et à changer de type:

 class Alternative'' a where empty'' :: a (<

>) :: a -> a -> a

Dans les deux cas, nous devons nous débarrasser de some , mais ce n’est pas grave. on peut les définir comme des fonctions autonomes avec le type (Applicative f, Alternative' f) => fa -> f [a] ou (Applicative f, Alternative'' (f [a])) => fa -> f [a] .

Maintenant, dans le second cas, où nous changeons le type de la variable type, nous voyons que notre classe est exactement la même que Monoid (ou, si vous voulez quand même supprimer empty'' , Semigroup ), il n’y a donc aucun avantage à avoir une classe séparée. Et en fait, même si nous laissons la variable kind seule mais en supprimant la contrainte Applicative , Alternative devient tout simplement forall a. Monoid (fa) forall a. Monoid (fa) , bien que nous ne puissions pas écrire ces contraintes quantifiées dans Haskell, même avec toutes les extensions fantastiques du GHC. (Notez que cela exprime le type interne – agnosticisme mentionné ci-dessus.) Ainsi, si nous pouvons faire l’un ou l’autre de ces changements, nous n’avons aucune raison de garder Alternative (sauf pour pouvoir exprimer cette contrainte quantifiée, mais cela semble peu convaincant) ).

Donc, la question se résume à «existe-t-il une relation entre les parties Alternative et les parties Applicative d’un f qui est une instance des deux?» Et bien qu’il n’y ait rien dans la documentation, je vais prendre position et dire oui – ou tout au moins, il devrait y en avoir. Je pense que Alternative est censé obéir à certaines lois relatives à l’ Applicative (en plus des lois monoïdes); en particulier, je pense que ces lois sont quelque chose comme

  1. Droite (de <*> ): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
  2. Bonne absorption (pour <*> ): empty <*> a = empty
  3. Dissortingbutivité à gauche (de fmap ): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
  4. Absorption à gauche (pour fmap ): f <$> empty = empty

Ces lois semblent être vraies pour [] et Maybe , et (en prétendant MonadPlus instance MonadPlus est une instance Alternative ), mais je n’ai pas fait de test ou de test exhaustif. (Par exemple, je pensais au départ que la dissortingbutivité restait réservée à <*> , mais cela «exécute les effets» dans le mauvais ordre pour [] .) Par analogie, il est vrai que MonadPlus doit obéir à des lois similaires (bien qu’il y ait apparemment une certaine ambiguïté à ce sujet ). J’avais à l’origine voulu revendiquer une troisième loi, qui semble naturelle:

  • Absorption à gauche (pour <*> ): a <*> empty = empty

Cependant, bien que je crois [] et que MaybeMaybe obéissent à cette loi, IO ne le fait pas, et je pense (pour des raisons qui apparaîtront dans les prochains paragraphes), il vaut mieux ne pas l’exiger.

Et en effet, il apparaît qu’Edward Kmett a des diapositives où il adopte une vision similaire; pour y arriver, nous devrons faire une brève digression impliquant un jargon plus mathématique. La diapositive finale, «Je veux plus de structure», dit que «un monoïde est à un applicatif comme un bon séminaire est une alternative», et «si vous rejetez l’argument d’un applicatif, vous obtenez un monoïde, si vous lancez loin de l’argument d’une alternative, vous obtenez un RightSemiNearRing. ”

Les bons séminaires? «Comment les bons séminaires ont-ils eu lieu?» Je vous entends pleurer. Bien,

Définition. Un quasi-semiring juste (aussi une bonne recherche , mais le premier semble être plus utilisé sur Google) est un quadruple ( R , +, ·, 0) où ( R , +, 0) est un monoïde, ( R , ·) est un semi-groupe, et les deux conditions suivantes sont réunies:

  1. · Est dissortingbutive a droite sur +: pour tout r , s , tR , ( s + t ) r = sr + tr .
  2. 0 est absorbant à droite pour:: pour tout rR , 0 r = 0.

Un quasi-semi-gauche est défini de manière analogue.

Maintenant, cela ne fonctionne pas tout à fait, car <*> n’est pas vraiment un opérateur associatif ou un opérateur binary – les types ne correspondent pas. Je pense que c’est ce que veut dire Edward Kmett quand il parle de «jeter l’argument». Une autre option pourrait être de dire (je ne suis pas sûr que ce soit correct) que nous voulons réellement ( fa , <|> , <*> , empty ) pour former un quasi-quiroidoïde droit , où le suffixe «-oid» indique que les opérateurs binarys ne peuvent être appliqués qu’à des paires d’éléments spécifiques (à la groupoids ). Et nous voudrions aussi dire que ( fa , <|> , <$> , empty ) était un quasi-demi-arête gauche, bien que cela puisse vraisemblablement découler de la combinaison des lois Applicative et de la structure quasi-semi-privée. Mais maintenant, je me mets à la tête, et de toute façon, ce n’est pas très pertinent.

En tout état de cause, ces lois, plus fortes que les lois monoïdes, signifient que des instances monoïdes parfaitement valides deviendraient des instances Alternative non valides. Il y a (au moins) deux exemples dans la bibliothèque standard: Monoid a => (a,) et Maybe . Regardons chacun d’eux rapidement.

Étant donné deux monoïdes, leur produit est un monoïde; par conséquent, les tuples peuvent devenir une instance de Monoid de manière évidente (reformater le source du paquet de base ):

 instance (Monoid a, Monoid b) => Monoid (a,b) where mempty = (mempty, mempty) (a1,b1) `mappend` (a2,b2) = (a1 `mappend` a2, b1 `mappend` b2) 

De même, on peut créer des tuples dont la première composante est un élément d’un monoïde dans une instance de Applicative en accumulant les éléments monoïdes (reformatant la source du paquet de base ):

 instance Monoid a => Applicative ((,) a) where pure x = (mempty, x) (u, f) <*> (v, x) = (u `mappend` v, fx) 

Cependant, les n-uplets ne sont pas une instance d’ Alternative , car ils ne le peuvent pas – la structure monoïdale sur Monoid a => (a,b) n’est pas présente pour tous les types b , et la structure monoïdale d’ Alternative doit être interne. tapez agnostic. Non seulement b doit être une monade, pour pouvoir exprimer (f <> g) <*> a , nous devons utiliser l’instance Monoid pour les fonctions, qui est pour les fonctions de la forme Monoid b => a -> b . Et même dans le cas où nous avons toute la structure monoïdale nécessaire, cela viole les quatre lois Alternative . Pour voir cela, soit ssf n = (Sum n, (<> Sum n)) et soit ssn = (Sum n, Sum n) . Ensuite, en écrivant (<>) pour mappend , nous obtenons les résultats suivants (qui peuvent être vérifiés dans GHCi, avec une annotation de type occasionnelle):

  1. Bonne dissortingbution:
    • (ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
    • (ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
  2. Bonne absorption:
    • mempty <*> ssn 1 = (Sum 1, Sum 0)
    • mempty = (Sum 0, Sum 0)
  3. Dissortingbutivité à gauche:
    • (<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
    • ((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
  4. Absorption à gauche:
    • (<> Sum 1) <$> mempty = (Sum 0, Sum 1)
    • mempty = (Sum 1, Sum 1)

Ensuite, considérez Maybe . Dans l’état actuel des choses, les instances Monoid et Alternative Maybe sont pas d’accord . (Bien que la discussion haskell-cafe que je mentionne au début de cette section propose de changer cela, il y a un nouveau type Option du paquetage semigroups qui produirait le même effet.) En tant que Monoid , MaybeMaybe ; Comme le paquetage de base n’a pas de classe semigroup, il ne fait que lever les monoïdes, et nous obtenons (reformatant le source du paquetage de base ):

 instance Monoid a => Monoid (Maybe a) where mempty = Nothing Nothing `mappend` m = m m `mappend` Nothing = m Just m1 `mappend` Just m2 = Just (m1 `mappend` m2) 

D’un autre côté, en tant Alternative , Maybe représente un choix prioritaire avec échec, et nous obtenons donc (reformatant à nouveau la source du paquet de base ):

 instance Alternative Maybe where empty = Nothing Nothing <|> r = r l <|> _ = l 

Et il s’avère que seul ce dernier satisfait Alternative lois Alternative . L’instance Monoid échoue moins mal que celle de (,) ; il obéit aux lois en ce qui concerne <*> , bien que presque par accident – il vient du comportement de la seule instance de Monoid pour les fonctions, qui (comme mentionné ci-dessus), soulève des fonctions qui renvoient les monoides dans le foncteur applicatif du lecteur. Si vous y parvenez (tout cela est très mécanique), vous constaterez que la bonne dissortingbutivité et la bonne absorption pour <*> tiennent toutes deux pour les instances Alternative et Monoid , tout comme l’absorption gauche pour fmap . Et la dissortingbutivité à gauche pour fmap est fmap pour l’instance Alternative , comme suit:

 f <$> (Nothing <|> b) = f <$> b by the definition of (<|>) = Nothing <|> (f <$> b) by the definition of (<|>) = (f <$> Nothing) <|> (f <$> b) by the definition of (<$>) f <$> (Just a <|> b) = f <$> Just a by the definition of (<|>) = Just (fa) by the definition of (<$>) = Just (fa) <|> (f <$> b) by the definition of (<|>) = (f <$> Just a) <|> (f <$> b) by the definition of (<$>) 

Cependant, il échoue pour l’instance Monoid ; en écrivant (<>) pour mappend , nous avons:

  • (<> Sum 1) <$> (Just (Sum 0) <> Just (Sum 0)) = Just (Sum 1)
  • ((<> Sum 1) <$> Just (Sum 0)) <> ((<> Sum 1) <$> Just (Sum 0)) = Just (Sum 2)

Maintenant, il y a une mise en garde à cet exemple. Si vous exigez seulement que Alternative s soit compatible avec <*> , et non avec <$> , alors Maybe est très bien. Les diapositives d’Edward Kmett, mentionnées ci-dessus, ne font pas référence à <$> , mais je pense qu’il semble raisonnable d’exiger des lois à cet égard également; néanmoins, je ne trouve rien pour me soutenir.

Ainsi, nous pouvons conclure qu’être une Alternative est une exigence plus forte que d’être un Monoid , et nécessite donc une classe différente. L’exemple le plus pur serait un type avec une instance Monoid agnostique de type interne et une instance Applicative incompatible entre elles; Cependant, il n’y en a pas dans le package de base, et je ne peux en penser à aucun. (Il est possible que cela n’existe pas, même si je serais surpris.) Néanmoins, ces exemples gnostiques de type interne démontrent pourquoi les deux classes de type doivent être différentes.


Quel est le but de la classe de type MonadPlus ?

MonadPlus , comme Alternative , est un renforcement de Monoid , mais en ce qui concerne Monad au lieu de Applicative . Selon Edward Kmett, dans sa réponse à la question «Distinction entre les types MonadPlus , Alternative et Monoid ?» , MonadPlus est aussi plus fort MonadPlus : la loi empty <*> a , par exemple, n’implique pas que empty >>= f . AndrewC en fournit deux exemples: Maybe and its dual. Le problème est compliqué par le fait qu’il existe deux ensembles de lois potentiels pour MonadPlus . Il est universellement admis que MonadPlus est supposé former un monoïde avec mplus et mempty , et qu’il est supposé satisfaire à la loi de zéro à gauche , mempty >>= f = mempty . Cependant, certains MonadPlus satisfont la dissortingbution gauche , mplus ab >>= f = mplus (a >>= f) (b >>= f) ; et d’autres satisfont la capture gauche , mplus (return a) b = return a . (Notez que le zéro / dissortingbution gauche pour MonadPlus est analogue à la dissortingbutivité / absorption droite pour Alternative ; (<*>) est plus analogue à (=<<) que (>>=) .) La dissortingbution gauche est probablement «meilleure», donc MonadPlus instance de MonadPlus qui répond aux MonadPlus , telle que Maybe , est une Alternative mais pas le premier type de MonadPlus . Et comme l'option de capture gauche repose sur la commande, vous pouvez imaginer un wrapper newtype pour Maybe dont l'instance Alternative est droite à la place de l'option gauche : a <|> Just b = Just b . Cela ne satisfera ni la dissortingbution de gauche ni la prise de gauche, mais sera une Alternative parfaitement valide.

Cependant, comme tout type qui est un MonadPlus devrait avoir son instance coïncide avec son instance Alternative (je crois que cela est nécessaire de la même manière qu'il est nécessaire que ap et (<*>) soient égaux pour Monad s qui sont Applicative s) ), vous pourriez imaginer définir la classe MonadPlus la place de

 class (Monad m, Alternative m) => MonadPlus' m 

La classe n'a pas besoin de déclarer de nouvelles fonctions; c'est juste une promesse sur les lois obéies par empty et (<|>) pour le type donné. Cette technique de conception n'est pas utilisée dans les bibliothèques standard Haskell, mais est utilisée dans certains packages plus mathématique à des fins similaires; Par exemple, le package lattices l' utilise pour exprimer l'idée qu'un réseau n'est qu'un semi- réseau de jointure et un semi- réseau de rencontre du même type, liés par des lois d'absorption.

La raison pour laquelle vous ne pouvez pas faire la même chose pour Alternative , même si vous vouliez garantir que Alternative et Monoid coïncidaient toujours, est dû au déséquilibre. La déclaration de classe souhaitée aurait la forme

 class (Applicative f, forall a. Monoid (fa)) => Alternative''' f 

mais (comme mentionné ci-dessus) pas même GHC Haskell supporte des contraintes quantifiées.

De plus, notez qu'avoir Alternative comme une super-classe de MonadPlus exigerait que Applicative soit une super-classe de Monad , donc bonne chance pour que cela se produise. Si vous rencontrez ce problème, il y a toujours le newtype WrappedMonad , qui transforme de manière évidente n'importe quelle Monad en Applicative ; il y a une instance MonadPlus m => Alternative (WrappedMonad m) where ... qui fait exactement ce que vous attendez.

 import Data.Monoid import Control.Applicative 

ZipList travers un exemple de la façon dont Monoid et Alternative interagissent avec le foncteur Maybe et le foncteur ZipList , mais commençons à partir de zéro, en partie pour que toutes les définitions soient fraîches dans notre esprit, en partie pour ne plus commuter , mais surtout pour que je puisse exécuter ce ghci passé pour corriger mes fautes de frappe!

 (<>) :: Monoid a => a -> a -> a (<>) = mappend -- I'll be using <> freely instead of `mappend`. 

Voici le clone Peut-être:

 data Perhaps a = Yes a | No deriving (Eq, Show) instance Functor Perhaps where fmap f (Yes a) = Yes (fa) fmap f No = No instance Applicative Perhaps where pure a = Yes a No <*> _ = No _ <*> No = No Yes f <*> Yes x = Yes (fx) 

et maintenant ZipList:

 data Zip a = Zip [a] deriving (Eq,Show) instance Functor Zip where fmap f (Zip xs) = Zip (map f xs) instance Applicative Zip where Zip fs <*> Zip xs = Zip (zipWith id fs xs) -- zip them up, applying the fs to the xs pure a = Zip (repeat a) -- infinite so that when you zip with something, lengths don't change 

Structure 1: combiner des éléments: Monoïde

Peut-être clone

D’abord, regardons Perhaps Ssortingng . Il y a deux manières de les combiner. Première concaténation

 (<++>) :: Perhaps Ssortingng -> Perhaps Ssortingng -> Perhaps Ssortingng Yes xs <++> Yes ys = Yes (xs ++ ys) Yes xs <++> No = Yes xs No <++> Yes ys = Yes ys No <++> No = No 

La concaténation fonctionne de manière inhérente au niveau Ssortingng, et non pas vraiment au niveau de l’indicatif, en traitant No comme si c’était Yes [] . C’est égal à liftA2 (++) . C’est sensé et utile, mais peut-être pourrions-nous généraliser l’utilisation de ++ pour utiliser n’importe quel moyen de combinaison – n’importe quel Monoïd!

 (<++>) :: Monoid a => Perhaps a -> Perhaps a -> Perhaps a Yes xs <++> Yes ys = Yes (xs `mappend` ys) Yes xs <++> No = Yes xs No <++> Yes ys = Yes ys No <++> No = No 

Cette structure monoïde pour Perhaps essaie de travailler autant que possible au niveau. Notez le Monoid a contrainte, en nous disant que nous utilisons la structure du niveau. Ce n’est pas une structure alternative, c’est une structure monoïde dérivée.

 instance Monoid a => Monoid (Perhaps a) where mappend = (<++>) mempty = No 

Ici, j’ai utilisé la structure des données pour append de la structure à l’ensemble. Si je combinais Set s, je pourrais append Ord a contexte Ord a place.

Clone ZipList

Alors, comment devrions-nous combiner des éléments avec un zipList? À quoi devraient-ils s’append si nous les combinons?

  Zip ["HELLO","MUM","HOW","ARE","YOU?"] <> Zip ["this", "is", "fun"] = Zip ["HELLO" ? "this", "MUM" ? "is", "HOW" ? "fun"] mempty = ["","","","",..] -- sensible zero element for zipping with ? 

Mais pour quoi devrions-nous l’utiliser ? . Je dis que le seul choix judicieux est ++ . En fait, pour les listes, (<>) = (++)

  Zip [Just 1, Nothing, Just 3, Just 4] <> Zip [Just 40, Just 70, Nothing] = Zip [Just 1 ? Just 40, Nothing ? Just 70, Just 3 ? Nothing] mempty = [Nothing, Nothing, Nothing, .....] -- sensible zero element 

Mais que pouvons-nous utiliser pour ? Je dis que nous sums censés combiner des éléments, nous devons donc utiliser l’opérateur de combinaison d’éléments à partir de Monoid: <> .

 instance Monoid a => Monoid (Zip a) where Zip as `mappend` Zip bs = Zip (zipWith (<>) as bs) -- zipWith the internal mappend mempty = Zip (repeat mempty) -- repeat the internal mempty 

C’est la seule façon sensée de combiner les éléments à l’aide d’un zip – c’est donc la seule instance de monoïde sensible.

Fait intéressant, cela ne fonctionne pas pour l’exemple Maybe ci-dessus, car Haskell ne sait pas combiner Int s – devrait-il utiliser + ou * ? Pour obtenir une instance Monoid sur des données numériques, placez-les dans Sum ou Product pour indiquer le monoïde à utiliser.

 Zip [Just (Sum 1), Nothing, Just (Sum 3), Just (Sum 4)] <> Zip [Just (Sum 40), Just (Sum 70), Nothing] = Zip [Just (Sum 41),Just (Sum 70), Just (Sum 3)] Zip [Product 5,Product 10,Product 15] <> Zip [Product 3, Product 4] = Zip [Product 15,Product 40] 

Point clé

Notez que le fait que le type dans un Monoïde ait du type * est exactement ce qui nous permet de placer le Monoid a contexte – nous pourrions aussi append Eq a ou Ord a . Dans un monoïde, les éléments bruts importent. Une instance Monoid est conçue pour vous permettre de manipuler et de combiner les données à l’intérieur de la structure.

Structure 2: choix de niveau supérieur: alternative

Un opérateur de choix est similaire, mais aussi différent.

Peut-être clone

 (<||>) :: Perhaps Ssortingng -> Perhaps Ssortingng -> Perhaps Ssortingng Yes xs <||> Yes ys = Yes xs -- if we can have both, choose the left one Yes xs <||> No = Yes xs No <||> Yes ys = Yes ys No <||> No = No 

Ici, il n’y a pas de concaténation – nous n’avons pas utilisé ++ du tout – cette combinaison fonctionne uniquement au niveau de Perhaps , changeons la signature de type en

 (<||>) :: Perhaps a -> Perhaps a -> Perhaps a Yes xs <||> Yes ys = Yes xs -- if we can have both, choose the left one Yes xs <||> No = Yes xs No <||> Yes ys = Yes ys No <||> No = No 

Notez qu’il n’y a pas de contrainte – nous n’utilisons pas la structure du niveau, mais simplement de la structure au niveau PerhapsPerhaps . Ceci est une structure alternative.

 instance Alternative Perhaps where (<|>) = (<||>) empty = No 

Clone ZipList

Comment devrions-nous choisir entre deux ziplistes?

 Zip [1,3,4] <|> Zip [10,20,30,40] = ???? 

Il serait très tentant d’utiliser <|> sur les éléments, mais nous ne le pouvons pas car le type des éléments ne nous est pas disponible. Commençons par le empty . Il ne peut pas utiliser un élément car nous ne connaissons pas le type des éléments lors de la définition d’une alternative, il doit donc être Zip [] . Nous avons besoin que ce soit une identité de gauche (et de préférence juste) pour <|> , donc

 Zip [] <|> Zip ys = Zip ys Zip xs <|> Zip [] = Zip xs 

Il y a deux choix judicieux pour Zip [1,3,4] <|> Zip [10,20,30,40] :

  1. Zip [1,3,4] parce que c’est le premier – compatible avec Maybe
  2. Zip [10,20,30,40] parce que c’est le plus long – compatible avec Zip [] étant éliminé

Eh bien, c’est facile à décider: puisque pure x = Zip (repeat x) , les deux listes peuvent être infinies, donc les comparer en termes de longueur pourrait ne jamais se terminer, il faut donc choisir le premier. Ainsi, la seule instance alternative sensible est:

 instance Alternative Zip where empty = Zip [] Zip [] <|> x = x Zip xs <|> _ = Zip xs 

C’est la seule alternative sensée que nous aurions pu définir. Remarquez comme il est différent de l’instance Monoid, car nous ne pouvions pas jouer avec les éléments, nous ne pouvions même pas les regarder.

Point clé

Notez que parce que Alternative prend un constructeur de type * -> * il n’y a aucun moyen possible d’append Monoid a contexte Ord a ou Eq a ou Monoid a . Une alternative n’est pas autorisée à utiliser des informations sur les données à l’intérieur de la structure. Vous ne pouvez pas, quel que soit le montant que vous souhaitez, faire quelque chose sur les données, sauf éventuellement les jeter.

Point clé: Quelle est la différence entre Alternative et Monoid?

Pas beaucoup – ils sont tous les deux des monoïdes, mais pour résumer les deux dernières sections:

Monoid * instances de Monoid * permettent de combiner des données internes. Alternative (* -> *) instances Alternative (* -> *) rendent cela impossible. Le monoïde offre de la flexibilité, Alternative fournit des garanties. Les types * et (* -> *) sont les principaux moteurs de cette différence. Les avoir tous les deux vous permet d’utiliser les deux types d’opérations.

C’est la bonne chose et nos deux saveurs sont appropriées. L’instance Monoïde pour Perhaps Ssortingng représente le regroupement de tous les caractères, l’instance Alternative représente un choix entre les chaînes.

Il n’y a rien de mal avec l’instance Monoid pour Maybe – elle fait son travail en combinant des données.
Il n’y a rien de mal avec l’instance Alternative pour Maybe – elle fait son travail, en choisissant entre les choses.

L’instance Monoid pour Zip combine ses éléments. L’instance alternative pour Zip est obligée de choisir l’une des listes – la première non vide.

C’est bien de pouvoir faire les deux.

Quel est le contexte applicatif utilisé?

Il y a une interaction entre choisir et appliquer. Voir les lois d’Antal SZ énoncées dans sa question ou au milieu de sa réponse ici.

D’un sharepoint vue pratique, c’est utile parce que Alternative est quelque chose qui est utilisé par certains foncteurs applicatifs. La fonctionnalité était utilisée pour les applications applicatives et une classe d’interface générale a donc été inventée. Les foncteurs applicatifs sont parfaits pour représenter des calculs qui produisent des valeurs (IO, Parser, élément d’entrée de l’interface utilisateur, etc.) et certains d’entre eux doivent gérer des défaillances. Une alternative est nécessaire.

Pourquoi Alternative a-t-il empty ?

Pourquoi Alternative a-t-il besoin d’une méthode / d’un membre vide? Je peux me tromper, mais il ne semble pas être utilisé du tout … du moins dans le code que je pourrais trouver. And it seems not to fit with the theme of the class — if I have two things, and need to pick one, what do I need an ’empty’ for?

That’s like asking why addition needs a 0 – if you want to add stuff, what’s the point in having something that doesn’t add anything? The answer is that 0 is the crucual pivotal number around which everything revolves in addition, just like 1 is crucial for multiplication, [] is crucial for lists (and y=e^x is crucial for calculus). In practical terms, you use these do-nothing elements to start your building:

 sum = foldr (+) 0 concat = foldr (++) [] msum = foldr (`mappend`) mempty -- any Monoid whichEverWorksFirst = foldr (<|>) empty -- any Alternative 

Can’t we replace MonadPlus with Monad+Alternative?

what’s the point of the MonadPlus type class? Can’t I unlock all of its goodness by just using something as both a Monad and Alternative? Why not just ditch it? (I’m sure I’m wrong, but I don’t have any counterexamples)

You’re not wrong, there aren’t any counterexamples!

Your interesting question has got Antal SZ, Petr Pudlák and I delved into what the relationship between MonadPlus and Applicative really is. The answer, here and here is that anything that’s a MonadPlus (in the left dissortingbution sense – follow links for details) is also an Alternative , but not the other way around.

This means that if you make an instance of Monad and MonadPlus, it satisfies the conditions for Applicative and Alternative anyway . This means if you follow the rules for MonadPlus (with left dist), you may as well have made your Monad an Applicative and used Alternative.

If we remove the MonadPlus class, though, we remove a sensible place for the rules to be documented, and you lose the ability to specify that something’s Alternative without being MonadPlus (which technically we ought to have done for Maybe). These are theoretical reasons. The practical reason is that it would break existing code. (Which is also why neither Applicative nor Functor are superclasses of Monad.)

Aren’t Alternative and Monoid the same? Aren’t Alternative and Monoid completely different?

the ‘pedia says that “the Alternative type class is for Applicative functors which also have a monoid structure.” I don’t get this — doesn’t Alternative mean something totally different from Monoid? ie I understood the point of the Alternative type class as picking between two things, whereas I understood Monoids as being about combining things.

Monoid and Alternative are two ways of getting one object from two in a sensible way. Maths doesn’t care whether you’re choosing, combining, mixing or blowing up your data, which is why Alternative was referred to as a Monoid for Applicative. You seem to be at home with that concept now, but you now say

for types that have both an Alternative and a Monoid instance, the instances are intended to be the same

I disagree with this, and I think my Maybe and ZipList examples are carefully explained as to why they’re different. If anything, I think it should be rare that they’re the same. I can only think of one example, plain lists, where this is appropriate. That’s because lists are a fundamental example of a monoid with ++ , but also lists are used in some contexts as an indeterminate choice of elements, so <|> should also be ++ .

Résumé

  • We need to define (instances that provide the same operations as) Monoid instances for some applicative functors, that genuinely combine at the applicative functor level, and not just lifting lower level monoids. The example error below from litvar = liftA2 mappend literal variable shows that <|> cannot in general be defined as liftA2 mappend ; <|> works in this case by combining parsers, not their data.

  • If we used Monoid directly, we’d need language extensions to define the instances. Alternative is higher kinded so you can make these instances without requiring language extensions.

Example: Parsers

Let’s imagine we’re parsing some declarations, so we import everything we’re going to need

 import Text.Parsec import Text.Parsec.Ssortingng import Control.Applicative ((<$>),(<*>),liftA2,empty) import Data.Monoid import Data.Char 

and think about how we’ll parse a type. We choose simplistic:

 data Type = Literal Ssortingng | Variable Ssortingng deriving Show examples = [Literal "Int",Variable "a"] 

Now let’s write a parser for literal types:

 literal :: Parser Type literal = fmap Literal $ (:) <$> upper <*> many alphaNum 

Meaning: parse an upper case character, then many alphaNum eric characters, combine the results into a single Ssortingng with the pure function (:) . Afterwards, apply the pure function Literal to turn those Ssortingng s into Type s. We’ll parse variable types exactly the same way, except for starting with a lower case letter:

 variable :: Parser Type variable = fmap Variable $ (:) <$> lower <*> many alphaNum 

That’s great, and parseTest literal "Bool" == Literal "Bool" exactly as we’d hoped.

Question 3a: If it’s to combine applicative’s effects with Monoid’s behavior, why not just liftA2 mappend

Edit:Oops – forgot to actually use <|> !
Now let’s combine these two parsers using Alternative:

 types :: Parser Type types = literal <|> variable 

This can parse any Type: parseTest types "Int" == Literal "Bool" and parseTest types "a" == Variable "a" . This combines the two parsers , not the two values . That’s the sense in which it works at the Applicative Functor level rather than the data level.

However, if we try:

 litvar = liftA2 mappend literal variable 

that would be asking the comstackr to combine the two values that they generate, at the data level. On a

 No instance for (Monoid Type) arising from a use of `mappend' Possible fix: add an instance declaration for (Monoid Type) In the first argument of `liftA2', namely `mappend' In the expression: liftA2 mappend literal variable In an equation for `litvar': litvar = liftA2 mappend literal variable 

So we found out the first thing; the Alternative class does something genuinely different to liftA2 mappend , becuase it combines objects at a different level – it combines the parsers, not the parsed data. If you like to think of it this way, it’s combination at the genuinely higher-kind level, not merely a lift. I don’t like saying it that way, because Parser Type has kind * , but it is true to say we’re combining the Parser s, not the Type s.

(Even for types with a Monoid instance, liftA2 mappend won’t give you the same parser as <|> . If you try it on Parser Ssortingng you’ll get liftA2 mappend which parses one after the other then concatenates, versus <|> which will try the first parser and default to the second if it failed.)

Question 3b: In what way does Alternative’s <|> :: fa -> fa -> fa differ from Monoid’s mappend :: b -> b -> b ?

Firstly, you’re right to note that it doesn’t provide new functionality over a Monoid instance.

Secondly, however, there’s an issue with using Monoid directly: Let’s try to use mappend on parsers, at the same time as showing it’s the same structure as Alternative :

 instance Monoid (Parser a) where mempty = empty mappend = (<|>) 

Oops! On a

 Illegal instance declaration for `Monoid (Parser a)' (All instance types must be of the form (T t1 ... tn) where T is not a synonym. Use -XTypeSynonymInstances if you want to disable this.) In the instance declaration for `Monoid (Parser a)' 

So if you have an applicative functor f , the Alternative instance shows that fa is a monoid, but you could only declare that as a Monoid with a language extension.

Once we add {-# LANGUAGE TypeSynonymInstances #-} at the top of the file, we’re fine and can define

 typeParser = literal `mappend` variable 

and to our delight, it works: parseTest typeParser "Yes" == Literal "Yes" and parseTest typeParser "a" == Literal "a" .

Even if you don’t have any synonyms ( Parser and Ssortingng are synonyms, so they’re out), you’ll still need {-# LANGUAGE FlexibleInstances #-} to define an instance like this one:

 data MyMaybe a = MyJust a | MyNothing deriving Show instance Monoid (MyMaybe Int) where mempty = MyNothing mappend MyNothing x = x mappend x MyNothing = x mappend (MyJust a) (MyJust b) = MyJust (a + b) 

(The monoid instance for Maybe gets around this by lifting the underlying monoid.)

Making a standard library unnecessarily dependent on language extensions is clearly undesirable.


So there you have it. Alternative is just Monoid for Applicative Functors (and isn’t just a lift of a Monoid). It needs the higher-kinded type fa -> fa -> fa so you can define one without language extensions.

Your other Questions, for completeness:

  1. Why does Alternative need an empty method/member?
    Because having an identity for an operation is sometimes useful. For example, you can define anyA = foldr (<|>) empty without using tedious edge cases.

  2. what’s the point of the MonadPlus type class? Can’t I unlock all of its goodness by just using something as both a Monad and Alternative? No. I refer you back to the question you linked to :

Moreover, even if Applicative was a superclass of Monad, you’d wind up needing the MonadPlus class anyways, because obeying empty <*> m = empty isn’t ssortingctly enough to prove that empty >>= f = empty .

….and I’ve come up with an example: Maybe. I explain in detail, with proof in this answer to Antal’s question. For the purposes of this answer, it’s worth noting that I was able to use >>= to make the MonadPlus instance that broke the Alternative laws.


Monoid structure is useful. Alternative is the best way of providing it for Applicative Functors.

I won’t cover MonadPlus because there is disagreement about its laws.


After trying and failing to find any meaningful examples in which the structure of an Applicative leads naturally to an Alternative instance that disagrees with its Monoid instance*, I finally came up with this:

Alternative’s laws are more ssortingct than Monoid’s, because the result cannot depend on the inner type. This excludes a large number of Monoid instances from being Alternatives. These datatypes allow partial (meaning that they only work for some inner types) Monoid instances which are forbidden by the extra ‘structure’ of the * -> * kind. Exemples:

  • the standard Maybe instance for Monoid assumes that the inner type is Monoid => not an Alternative

  • ZipLists, tuples, and functions can all be made Monoids, if their inner types are Monoids => not Alternatives

  • sequences that have at least one element — cannot be Alternatives because there’s no empty :

     data Seq a = End a | Cons a (Seq a) deriving (Show, Eq, Ord) 

On the other hand, some data types cannot be made Alternatives because they’re * -kinded:

  • unit — ()
  • Ordering
  • numbers, booleans

My inferred conclusion: for types that have both an Alternative and a Monoid instance, the instances are intended to be the same. Voir aussi cette réponse .


excluding Maybe, which I argue doesn’t count because its standard instance should not require Monoid for the inner type, in which case it would be identical to Alternative

I understood the point of the Alternative type class as picking between two things, whereas I understood Monoids as being about combining things.

If you think about this for a moment, they are the same.

The + combines things (usually numbers), and it’s type signature is Int -> Int -> Int (or whatever).

The <|> operator selects between alternatives, and it’s type signature is also the same: take two matching things and return a combined thing.