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.
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.
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.
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.
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 duMonoid
?
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 × M → M , noté par juxtaposition, de sorte que les deux conditions suivantes sont réunies:
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 m ₁ m ₂ 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 m ₁ m ₂ correspond à un choix entre m ₁ et m ₂. Ceci est l’intuition «picking». Notez que les deux obéissent aux lois du monoïde:
(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 m ₂ m ≠ m ₂ m ₁ .)
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:
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 contrainteApplicative
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
<*>
): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
<*>
): empty <*> a = empty
fmap
): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
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:
<*>
): a <*> empty = empty
Cependant, bien que je crois []
et que Maybe
– Maybe
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:
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):
(ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
(ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
mempty <*> ssn 1 = (Sum 1, Sum 0)
mempty = (Sum 0, Sum 0)
(<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
(<> 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
, Maybe
– Maybe
; 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
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.
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 Perhaps
– Perhaps
. 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]
:
Zip [1,3,4]
parce que c’est le premier – compatible avec Maybe 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.
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.
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.
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
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.)
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 ++
.
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.
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.
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.)
<|> :: 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.
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.
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 thatempty >>= 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:
()
Ordering
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.