Pourquoi Applicative devrait-elle être une superclasse de Monad ?

Question

Étant donné :

Applicative m, Monad m => mf :: m (a -> b), ma :: m a

il semble être considéré comme une loi que :

mf <*> ma === do { f <- mf; a <- ma; return (f a) }

ou de manière plus concise :

(<*>) === ap

Le site la documentation pour Control.Applicative dit que <*> est "application séquentielle", et cela suggère que (<*>) = ap . Cela signifie que <*> doit évaluer les effets de manière séquentielle, de gauche à droite, pour des raisons de cohérence avec les règles de l'UE. >>= ... Mais ça ne va pas. L'article original de McBride et Paterson semble impliquer que le séquençage de gauche à droite est arbitraire :

La monade IO, et d'ailleurs toute monade, peut être rendue Applicative en prenant pure = return et <*> = ap . Nous pourrions également utiliser la variante de ap qui effectue les calculs dans l'ordre inverse mais nous nous en tiendrons à l'ordre de gauche à droite dans ce document.

Il y a donc deux des dérivations légales, non triviales pour <*> qui découlent de >>= et return avec un comportement distinct. Et dans certains cas, ni de ces deux dérivations sont souhaitables.

Par exemple, le (<*>) === ap forces de l'ordre Validation des données pour définir deux types de données distincts : Validation et AccValidation . Le premier a un Monad instance similaire à SaufT et un Applicative qui est d'une utilité limitée, puisqu'elle s'arrête après la première erreur. Cette dernière, par contre, ne définit pas une instance de Monad et est donc libre d'implémenter une instance Applicative qui, bien plus utilement, accumule les erreurs.

Il y a eu quelques discussion à ce sujet précédemment sur StackOverflow, mais je ne pense pas qu'il ait vraiment répondu à la question :

Pourquoi cela devrait-il être une loi ?

Les autres lois relatives aux foncteurs, aux applicatifs et aux monades - telles que l'identité, l'associativité, etc. - expriment certaines propriétés mathématiques fondamentales de ces structures. Nous pouvons mettre en œuvre diverses optimisations en utilisant ces lois et prouver des choses sur notre propre code en les utilisant. En revanche, j'ai l'impression que les (<*>) === ap La loi impose une contrainte arbitraire sans avantage correspondant.

Pour ce que ça vaut, je préférerais abandonner la loi en faveur de quelque chose comme ça :

newtype LeftA m a = LeftA (m a)
instance Monad m => Applicative (LeftA m) where
  pure = return
  mf <*> ma = do { f <- mf; a <- ma; return (f a) }

newtype RightA m a = RightA (m a)
instance Monad m => Applicative (RightA m) where
  pure = return
  mf <*> ma = do { a <- ma; f <- mf; return (f a) }

Je pense que cela rend correctement la relation entre les deux, sans contraindre indûment l'un ou l'autre.

Donc, quelques angles pour aborder la question :

• Y a-t-il d'autres lois relatives Monad et Applicative ?
• Y a-t-il une raison mathématique inhérente à l'enchaînement des effets pour Applicative de la même manière qu'ils le font pour Monad ?
• Est-ce que GHC ou tout autre outil effectue des transformations de code qui supposent/exigent que cette loi soit vraie ?
• Pourquoi le Monade-foncteur-applicative La proposition de la Commission européenne est-elle considérée comme une bonne chose ? (Les citations seraient très appréciées ici).

Et une question bonus :

• Comment Alternative et MonadPlus dans tout ça ?

---

Note : modification majeure pour clarifier l'essentiel de la question. La réponse postée par @duplode cite une version antérieure.

Answer 1

Je ne suis pas très satisfait des réponses données jusqu'à présent, mais je pense que les commentaires qui y sont associés sont un peu plus convaincants. Je vais donc les résumer ici :

---

Je pense qu'il n'y a qu'un seul sens Functor instance qui découle de Applicative :

fmap f fa = pure f <*> fa

En supposant que c'est unique, il est logique que Functor devrait être une superclasse de Applicative avec cette loi. De même, je pense qu'il n'y a qu'une seule solution raisonnable Functor instance qui découle de Monad :

fmap f fa = fa >>= return . f

Donc, encore une fois, il est logique que Functor devrait être une superclasse de Monad . L'objection que j'avais (et que j'ai toujours), c'est qu'il y a deux façons raisonnables d'aborder le problème. Applicative les instances qui découlent de Monad et, dans certains cas spécifiques, encore plus qui sont légaux ; alors pourquoi en imposer un ?

porcherie (premier auteur du original Applicative papier ) écrit :

"Bien sûr que ça ne suit pas. C'est un choix."

(sur twitter ) : "la notation do est une punition injuste pour avoir travaillé dans une monade ; nous méritons une notation applicative".

duplode écrit de la même façon :

"...il est juste de dire que pure === return et (<*>) === ap ne sont pas des lois au sens fort, c'est-à-dire que les lois de la monade sont ainsi..."

"Sur le LeftA / RightA idée : il y a des cas comparables ailleurs dans les bibliothèques standard (par ex. Sum et Product sur Data.Monoid ). Le problème de faire la même chose avec Applicative est que le rapport puissance/poids est trop faible pour justifier la précision/flexibilité supplémentaire. Les nouveaux types rendraient le style applicatif beaucoup moins agréable à utiliser."

Je suis donc heureux de voir ce choix énoncé explicitement, justifié par le simple raisonnement qu'il facilite les cas les plus courants.

Answer 2

Entre autres choses, vous demandez pourquoi le Functor-Applicative-Monad une bonne chose. L'une des raisons est que le manque d'unité signifie qu'il y a beaucoup de duplication de l'API. Considérez la norme Control.Monad module. Voici les fonctions de ce module qui utilisent essentiellement la fonction Monad (il n'y en a pas pour MonadPlus ) :

(>>=) fail (=<<) (>=>) (<=<) join foldM foldM_

Voici les fonctions de ce module dans lesquelles un Monad / MonadPlus Pour autant que je sache, la contrainte pourrait facilement être assouplie à Applicative / Alternative :

(>>) return mzero mplus mapM mapM_ forM forM_ sequence sequence_ forever
msum filterM mapAndUnzipM zipWithM zipWithM_ replicateM replicateM_ guard
when unless liftM liftM2 liftM3 liftM4 liftM5 ap

Beaucoup de ce dernier groupe faire ont Applicative ou Alternative dans l'une ou l'autre des versions suivantes Control.Applicative , Data.Foldable ou Data.Traversable - mais pourquoi avoir besoin d'apprendre toute cette duplication en premier lieu ?

Answer 3

et dans ma propre intuition (peut-être erronée), étant donné pure f <*> ma <*> mb il n'est pas nécessaire d'établir une séquence prédéterminée, car aucune des valeurs ne dépend des autres.

Les valeurs ne le sont pas, mais les effets le sont. (<*>) :: t (a -> b) -> t a -> t b signifie que vous devez d'une manière ou d'une autre combiner les effets des arguments afin d'obtenir les effets globaux. Le fait que la combinaison soit commutative ou non dépend de la manière dont l'instance est définie. Par exemple, l'instance de Maybe est commutative, alors que l'instance par défaut de "jointure croisée" pour les listes ne l'est pas. Par conséquent, il existe des cas dans lesquels vous ne pouvez pas éviter d'imposer un peu de l'ordre.

Quelles sont les lois, s'il y en a, qui relient Monad et Applicative ?

Bien qu'il soit juste de dire que pure === return et (<*>) === ap (citant Control.Applicative ) ne sont pas des lois au sens fort du terme, comme c'est le cas pour les lois des monades, mais elles permettent de garder les instances sans surprise. Étant donné que chaque Monad donne lieu à une instance de Applicative (en fait deux instances, comme vous le soulignez), il est naturel que l'instance réelle de Applicative correspond à ce que Monad nous donne. Quant à la convention de gauche à droite, en suivant l'ordre de ap et liftM2 (qui existait déjà à l'époque où Applicative a été introduit, et qui reflète l'ordre imposé par (>>=) ) était une décision judicieuse. (Notez que, si nous ignorons pour un moment combien (>>=) en pratique, le choix opposé serait également défendable, car il rendrait (<*>) et (=<<) qui ont des types analogues, enchaînent les effets dans le même ordre).

Est-ce que GHC ou tout autre outil effectue des transformations de code qui supposent/exigent que cette loi soit vraie ?

Cela semble très peu probable étant donné que Applicative n'est même pas une superclasse de Monad ( mais ). Ces "lois" permettent toutefois aux lecteurs du code d'effectuer les transformations, ce qui est tout aussi important.

N.B. : Si vous avez besoin d'inverser l'ordre des effets dans un fichier de type Applicative Par exemple, il y a Control.Applicative.Backwards comme l'a souligné Gabriel Gonzalez. Et aussi, (<**>) inverse les arguments mais continue de séquencer les effets de gauche à droite, il peut donc également être utilisé pour inverser le séquençage. De même, (<*) n'est pas flip (*>) car les deux effets se succèdent de gauche à droite.