tipos - modulos haskell

Confundido por el significado de la clase de tipo ''Alternativa'' y su relación con otras clases de tipo

Question

He estado revisando Typeclassopedia para aprender las clases de tipos. Estoy atrapado entendiendo Alternative (y MonadPlus , para el caso).

Los problemas que estoy teniendo:

• la ''pedia dice que "la clase de tipo alternativa es para los funtores Aplicativos que también tienen una estructura monoide". No entiendo esto, ¿no significa Alternativa algo totalmente diferente de Monoid? es decir, entendí el punto de la clase de tipo Alternativo como escoger entre dos cosas, mientras que entendí que Monoids se trata de combinar cosas.

• ¿Por qué Alternative necesita un método / miembro empty ? Puedo estar equivocado, pero parece que no se usa en absoluto ... al menos en el code que pude encontrar. Y parece que no encaja con el tema de la clase: si tengo dos cosas, y necesito elegir una, ¿para qué necesito un ''vacío''?

• ¿Por qué la clase de tipo Alternativa necesita una restricción Aplicativa y por qué necesita un tipo de * -> * ? ¿Por qué no solo tener <|> :: a -> a -> a ? Todas las instancias podrían implementarse de la misma manera ... creo (no estoy seguro). ¿Qué valor proporciona que Monoid no lo haga?

• ¿ MonadPlus es el punto de la clase de tipo MonadPlus ? ¿No puedo desbloquear todas sus bondades simplemente usando algo como una Monad y una Alternative ? ¿Por qué no solo abandonarlo? (Estoy seguro de que estoy equivocado, pero no tengo contraejemplos)

Espero que todas esas preguntas sean coherentes ...!

Actualización de Bounty: la respuesta de @Antal es un gran comienzo, pero Q3 todavía está abierto: ¿qué ofrece Alternative que no sea Monoid? Encuentro esta respuesta insatisfactoria ya que carece de ejemplos concretos, y una discusión específica de cómo el mayor grado de Alianza lo distingue de Monoid.

Si se trata de combinar los efectos aplicativos con el comportamiento de Monoid, ¿por qué no simplemente:

liftA2 mappend

Esto es aún más confuso para mí porque muchas instancias de Monoid son exactamente las mismas que las instancias alternativas.

Es por eso que estoy buscando ejemplos específicos que muestren por qué Alternative es necesario, y cómo es diferente, o significa algo diferente, de Monoid.

Answer 1

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.

El +combina cosas (generalmente números), y su tipo de firma es Int -> Int -> Int(o lo que sea).

El <|>operador selecciona entre alternativas, y su firma de tipo también es la misma: tome dos cosas que coincidan y devuelva una combinación.

Answer 2

Resumen

• 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.String
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 String | Variable String  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 String with the pure function (:) . Afterwards, apply the pure function Literal to turn those String 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 compiler to combine the two values that they generate, at the data level. We get

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 String 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! We get

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 String 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 strictly 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.

Answer 3

Para empezar, permítanme ofrecer respuestas cortas a cada una de estas preguntas. Luego expandiré cada una de ellas en una respuesta más detallada, pero espero que estas breves ayuden a navegar por ellas.

1. No, Alternative y Monoid no significan cosas diferentes; Alternative es para tipos que tienen la estructura tanto de Applicative como de Monoid . "Escoger" y "combinar" son dos intuiciones diferentes para el mismo concepto más amplio.

2. Alternative contiene tanto empty como <|> porque los diseñadores pensaron que sería útil y porque da lugar a un monoide. En términos de selección, empty corresponde a hacer una elección imposible.

3. Necesitamos tanto Alternative como Monoid porque el primero obedece (o debería) más leyes que el segundo; estas leyes relacionan la estructura monoidal y aplicativa del constructor de tipo. Además, Alternative no puede depender del tipo interno, mientras que Monoid puede.

4. MonadPlus es un poco más fuerte que Alternative , ya que debe obedecer más leyes; estas leyes relacionan la estructura monoidal con la estructura monádica además de la estructura aplicativa. Si tiene instancias de ambos, deben coincidir.

¿La Alternative no significa algo totalmente diferente de Monoid ?

¡Realmente no! Parte de la razón de su confusión es que la clase Haskell Monoid usa algunos nombres bastante malos (bueno, insuficientemente generales). Así es como un matemático definiría un monoide (siendo muy explícito al respecto):

Definición. Un monoide es un conjunto M equipado con un elemento distinguido ε ∈ M y un operador binario ·: M × M → M , denotado por yuxtaposición, de modo que se cumplen las dos condiciones siguientes:

1. ε es la identidad: para todo m ∈ M , m ε = ε m = m .
2. · Es asociativo: para todo m ₁, m ₂, m ₃, M , ( m ₁ m ₂) m ₃ = m ₁ ( m ₂ m ₃).

Eso es. En Haskell, ε se deletrea mempty y · se escribe mappend (o, en estos días, <> ), y el conjunto M es el tipo M en el instance Monoid M where ...

Al observar esta definición, vemos que no dice nada sobre "combinar" (o sobre "escoger", para el caso). Dice cosas sobre · y sobre ε , pero eso es todo. Ahora bien, es cierto que combinar cosas funciona bien con esta estructura: ε equivale a no tener nada, y m ₁ m ₂ dice que si mezclo m ₁ y m ₂ juntas, puedo obtener algo nuevo que contenga todas sus cosas. Pero aquí hay una intuición alternativa: ε no corresponde a ninguna elección, y m ₁ m ₂ corresponde a una elección entre m ₁ y m ₂. Esta es la intuición de "escoger". Tenga en cuenta que ambos obedecen las leyes de monoid:

1. No tener nada en absoluto y no tener otra opción son la identidad.
   • Si no tengo nada y lo combino con algunas cosas, termino con las mismas cosas otra vez.
   • Si tengo que elegir entre ninguna opción (algo imposible) y alguna otra opción, tengo que escoger la otra opción (posible).
2. Las colecciones Glomming juntas y la elección son ambas asociativas.
   • Si tengo tres colecciones de cosas, no importa si mezclo las dos primeras juntas y luego la tercera, o las dos últimas juntas y luego la primera; De cualquier manera, termino con la misma colección glommed total.
   • Si puedo elegir entre tres cosas, no importa si (a) primero elijo entre primero o segundo y tercero y luego, si es necesario, entre primero y segundo, o (b) primero elijo entre primero y segundo o tercero y luego, si es necesario, entre el segundo y el tercero. De cualquier manera, puedo elegir lo que quiero.

(Nota: estoy jugando rápido y suelto aquí, es por eso que es intuición. Por ejemplo, es importante recordar que · no es necesario que sea conmutativa, lo cual se pasa por alto: es perfectamente posible que m ₁ m ₂ m ₂ m ₁ .)

He aquí: tanto este tipo de cosas (y muchas otras) son números multiplicados que realmente "combinan" o "seleccionan"?) Obedecen las mismas reglas. Tener una intuición es importante para desarrollar la comprensión, pero son las reglas y las definiciones las que determinan lo que realmente está sucediendo.

¡Y la mejor parte es que estas dos intuiciones pueden ser interpretadas por el mismo proveedor! Sea M un conjunto de conjuntos (¡no un conjunto de todos los conjuntos!) Que contiene el conjunto vacío, sea ε el conjunto vacío ∅, y permita · establecer la unión ∪. Es fácil ver que ∅ es una identidad para ∪, y que ∪ es asociativa, por lo que podemos concluir que ( M , ∅, ∪) es un monoide. Ahora:

1. Si pensamos en los conjuntos como conjuntos de cosas, entonces ∪ corresponde apretarlos para obtener más cosas: la intuición de "combinación".
2. Si pensamos que los conjuntos representan acciones posibles, entonces ∪ corresponde al aumento de su grupo de posibles acciones para elegir la intuición de "escoger".

Y esto es exactamente lo que sucede con [] en Haskell: [a] es un Monoid para todo a , y [] como un functor aplicativo (y una mónada) se usa para representar el no determinismo. Ambas intuiciones coinciden y se combinan en el mismo tipo: mempty = empty = [] y mappend = (<|>) = (++) .

Entonces, la clase Alternative está ahí para representar objetos que (a) son funtores aplicativos, y (b) cuando son instanciados en un tipo, tienen un valor y una función binaria que siguen algunas reglas. ¿Qué reglas? El monoide gobierna ¿Por qué? Porque resulta útil :-)

¿Por qué Alternative necesita un método / miembro vacío?

Bueno, la respuesta sarcástica es "porque la Alternative representa una estructura monoide". Pero la verdadera pregunta es: ¿por qué una estructura monoide? ¿Por qué no solo un semigrupo, un monoide sin ε ? Una respuesta es afirmar que los monoides son simplemente más útiles. Creo que muchas personas (pero tal vez no Edward Kmett ) estarían de acuerdo con esto; casi todo el tiempo, si tiene un sensible (<|>) / mappend / ·, podrá definir un sentido empty / mempty / ε . Por otro lado, tener la generalidad adicional es agradable, ya que te permite colocar más cosas bajo el paraguas.

También quiere saber cómo esto se combina con la intuición de "escoger". Teniendo en cuenta que, en cierto sentido, la respuesta correcta es "saber cuándo abandonar la intuición de ''escoger''," creo que puedes unificar los dos. Considere [] , el functor aplicativo para el no determinismo. Si combino dos valores de tipo [a] con (<|>) , eso corresponde a una acción no determinista desde la izquierda o desde la derecha. Pero a veces, no vas a tener acciones posibles en un lado, y eso está bien. Del mismo modo, si consideramos analizadores sintácticos, (<|>) representa un analizador que analiza lo que está a la izquierda o lo que está a la derecha ("recoge"). Y si tiene un analizador que siempre falla, eso termina siendo una identidad: si lo elige, inmediatamente rechaza esa selección y prueba con la otra.

Dicho todo esto, recuerda que sería completamente posible tener una clase casi como Alternative , pero carente de empty . Eso sería perfectamente válido, incluso podría ser una superclase de Alternative pero no es lo que Haskell hizo. Es de suponer que esto está fuera de toda duda sobre lo que es útil.

¿Por qué la clase de tipo Alternative necesita una restricción Applicative y por qué necesita un tipo de * -> * ? ... ¿Por qué no solo [use] liftA2 mappend ?

Bueno, consideremos cada uno de estos tres cambios propuestos: deshacerse de la restricción Applicative para Alternative ; cambiando el tipo de argumento de la Alternative ; y usar liftA2 mappend lugar de <|> y pure mempty lugar de empty . Veremos este tercer cambio primero, ya que es el más diferente. Supongamos que nos deshacemos completamente de Alternative , y reemplazamos la clase con dos funciones simples:

fempty :: (Applicative f, Monoid a) => f a
fempty = pure mempty

(>|<) :: (Applicative f, Monoid a) => f a -> f a -> f a
(>|<) = liftA2 mappend

Incluso podríamos mantener las definiciones de some y many . Y esto nos da una estructura monoide, es verdad. Pero parece que nos da el error. ¿Debería Just fst >|< Just snd fail, ya que (a,a) -> a no es una instancia de Monoid ? No, pero eso es lo que produciría el código anterior. La instancia de monoid que queremos es una que es agnóstica de tipo interno (para tomar prestada la terminología de Matthew Farkas-Dyck en una discusión de haskell-café muy relacionada que plantea algunas preguntas muy similares); la estructura Alternative es sobre un monoide determinado por la estructura de f , no la estructura del argumento de f .

Ahora que creemos que queremos dejar Alternative como un tipo de clase de tipo, veamos las dos formas propuestas para cambiarlo. Si cambiamos el tipo, tenemos que deshacernos de la restricción Applicative ; Applicative solo habla de cosas de su tipo * -> * , por lo que no hay forma de referirse a él. Eso deja dos posibles cambios; el primer cambio, más leve, es deshacerse de la restricción Applicative pero deje el tipo solo:

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

El otro cambio más grande es deshacerse de la restricción Applicative y cambiar el tipo:

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

En ambos casos, tenemos que deshacernos de some / many , pero eso está bien; podemos definirlos como funciones independientes con el tipo (Applicative f, Alternative'' f) => fa -> f [a] o (Applicative f, Alternative'''' (f [a])) => fa -> f [a]

Ahora, en el segundo caso, donde cambiamos el tipo de variable de tipo, vemos que nuestra clase es exactamente igual a Monoid (o, si aún desea eliminar empty'''' Semigroup empty'''' Semigroup ), entonces no hay ventaja de tener una clase separada. Y, de hecho, incluso si dejamos la variable tipo solo, pero eliminamos la restricción Applicative , la Alternative simplemente se convierte forall a. Monoid (fa) forall a. Monoid (fa) , aunque no podemos escribir estas restricciones cuantificadas en Haskell, ni siquiera con todas las lujosas extensiones de GHC. (Nótese que esto expresa el agnosticismo de tipo interno mencionado anteriormente). Por lo tanto, si podemos hacer cualquiera de estos cambios, entonces no tenemos ninguna razón para mantener la Alternative (a excepción de poder expresar esa restricción cuantificada, pero eso difícilmente parece convincente )

Entonces la pregunta se reduce a "¿existe una relación entre las partes Alternative y las partes Applicative de una f que es una instancia de ambas?" Y aunque no hay nada en la documentación, voy a tomar una posición y decir que sí , o al menos, debería haberlo . Creo que se supone que Alternative debe obedecer algunas leyes relacionadas con Applicative (además de las leyes monoid); en particular, creo que esas leyes son algo así como

1. Distributividad derecha (de <*> ): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
2. Absorción derecha (para <*> ): empty <*> a = empty
3. Distributividad izquierda (de fmap ): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
4. Absorción izquierda (para fmap ): f <$> empty = empty

Estas leyes parecen ser verdaderas para [] y Maybe , y (pretendiendo que su instancia de MonadPlus es una instancia Alternative ) IO , pero no he hecho ninguna prueba o prueba exhaustiva. (Por ejemplo, originalmente pensé que la distributividad izquierda se mantuvo para <*> , pero esto "realiza los efectos" en el orden incorrecto para [] ). Sin embargo, a modo de analogía, es cierto que se espera que MonadPlus obedezca leyes similares (aunque aparentemente hay cierta ambigüedad sobre qué ). Originalmente quería reclamar una tercera ley, que parece natural:

• Absorción izquierda (para <*> ): a <*> empty = empty

Sin embargo, aunque creo [] y Maybe obedezca esta ley, IO no lo hace, y creo que (por razones que se pondrán de manifiesto en los próximos párrafos) es mejor no exigirlo.

Y, de hecho, parece que Edward Kmett tiene algunos toboganes donde defiende una visión similar; para entrar en eso, necesitaremos tomar una breve digresión que involucre algo más de jerga matemática. La diapositiva final, "Quiero más estructura", dice que "Un monoide es para un aplicativo como una minería alternativa es para una alternativa", y "Si desechas el argumento de un aplicativo, obtienes un Monóide, si lo arrojas". lejos del argumento de una Alternativa obtienes un RightSemiNearRing ".

Seminegrados derecho? "¿Cómo se metieron las semineladas correctas?" Te escucho llorar. Bien,

Definición. Un semiacumado derecho (también derecho de seminar , pero el primero parece usarse más en Google) es un cuádruple ( R , +, ·, 0) donde ( R , +, 0) es un monoide, ( R , ·) es un semigrupo y se cumplen las dos condiciones siguientes:

1. · Es correcto-distributivo sobre +: para todo r , s , t ∈ R , ( s + t ) r = sr + tr .
2. 0 absorbe bien para ·: para todos r ∈ R , 0 r = 0.

Un semielaborado izquierdo se define análogamente.

Ahora, esto no funciona, porque <*> no es realmente asociativo o un operador binario; los tipos no coinciden. Creo que esto es a lo que Edward Kmett llega cuando habla de "tirar la discusión". Otra opción podría ser decir (no estoy seguro si esto es correcto) que realmente queremos ( fa , <|> , <*> , empty ) para formar un derecho casi semiringoide , donde el sufijo "-oid" indica que los operadores binarios solo se pueden aplicar a pares específicos de elementos (à la groupoids ). Y también quisiéramos decir que ( fa , <|> , <$> , empty ) era casi semiringoide izquierdo, aunque esto podría ser el resultado de la combinación de las leyes Applicative y la estructura semiringoide derecha. Pero ahora me estoy volviendo loco, y esto no es muy relevante de todos modos.

En cualquier caso, estas leyes, al ser más fuertes que las leyes de monoid, significan que las instancias de Monoid perfectamente válidas se volverían inválidas. Instancias Alternative . Hay (al menos) dos ejemplos de esto en la biblioteca estándar: Monoid a => (a,) y Maybe . Miremos cada uno de ellos rápidamente.

Dado dos monoides cualquiera, su producto es un monoide; en consecuencia, las tuplas se pueden convertir en una instancia de Monoid de la manera más obvia (reformateo de la fuente del paquete 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 manera similar, podemos hacer que las tuplas cuyo primer componente sea un elemento de un monoide en una instancia de Applicative al acumular los elementos monoides (formateando la fuente del paquete base ):

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

Sin embargo, las tuplas no son un ejemplo de Alternative , porque no pueden ser: la estructura monoidal sobre Monoid a => (a,b) no está presente para todos los tipos b , y la estructura monoidal de la Alternative debe ser interna. tipo agnóstico No solo debe ser una mónada, para poder expresar (f <> g) <*> a , necesitamos usar la instancia de Monoid para funciones, que es para funciones de la forma Monoid b => a -> b . E incluso en el caso de que tengamos toda la estructura monoidal necesaria, viola las cuatro leyes Alternative . Para ver esto, deje ssf n = (Sum n, (<> Sum n)) y deje ssn = (Sum n, Sum n) . Luego, escribiendo (<>) para mappend , obtenemos los siguientes resultados (que se pueden verificar en GHCi, con la anotación de tipo ocasional):

1. Distributividad correcta:
   • (ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
   • (ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
2. Absorción correcta:
   • mempty <*> ssn 1 = (Sum 1, Sum 0)
   • mempty = (Sum 0, Sum 0)
3. Distributividad izquierda:
   • (<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
   • ((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
4. Absorción izquierda:
   • (<> Sum 1) <$> mempty = (Sum 0, Sum 1)
   • mempty = (Sum 1, Sum 1)

Luego, considera Maybe . Tal como está, las instancias Monoid y Alternative Maybe no están de acuerdo . (Aunque la discusión de haskell-cafe que menciono al comienzo de esta sección propone cambiar esto, existe un tipo de Option Nuevo del paquete de semigrupos que produciría el mismo efecto.) Como Monoid , Maybe levanta semigrupos en monoides al usar Nothing como identidad ; dado que el paquete base no tiene una clase de semigrupo, simplemente levanta los monoides, y entonces obtenemos (formateo de la fuente del paquete 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)

Por otro lado, como Alternative , Maybe representa la elección priorizada con falla, y así obtenemos (volviendo a formatear la fuente del paquete base ):

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

Y resulta que solo este último satisface las leyes Alternative . La instancia de Monoid falla menos que (,) ''s; obedece las leyes con respecto a <*> , aunque casi por accidente proviene del comportamiento de la única instancia de Monoid para funciones, que (como se mencionó anteriormente), levanta funciones que devuelven monoides al funtor aplicativo del lector. Si lo resuelves (todo es muy mecánico), encontrarás que la distribución correcta y la absorción correcta para <*> son fmap tanto para las instancias Alternative como para fmap , al igual que la absorción izquierda para fmap . Y la distributividad izquierda de fmap se mantiene para la instancia Alternative , de la siguiente manera:

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 (f a)                       by the definition of (<$>)
  = Just (f a) <|> (f <$> b)         by the definition of (<|>)
  = (f <$> Just a) <|> (f <$> b)     by the definition of (<$>)

Sin embargo, falla para la instancia de Monoid ; escribiendo (<>) para mappend , tenemos:

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

Ahora, hay una advertencia a este ejemplo. Si solo requiere que la Alternative s sea compatible con <*> , y no con <$> , entonces Maybe esté bien. Las diapositivas de Edward Kmett, mencionadas anteriormente, no hacen referencia a <$> , pero creo que parece razonable exigir leyes con respecto a eso también; sin embargo, no puedo encontrar nada que me respalde en esto.

Por lo tanto, podemos concluir que ser una Alternative es un requisito más fuerte que ser un Monoid , por lo que requiere una clase diferente. El ejemplo más puro de esto sería un tipo con una instancia Monoid agnóstica de tipo interno y una instancia Applicative que fueran incompatibles entre sí; sin embargo, no hay ninguno de esos tipos en el paquete base, y no puedo pensar en ninguno. (Es posible que ninguno exista, aunque me sorprendería.) Sin embargo, estos ejemplos gnósticos de tipo interno demuestran por qué las dos clases de tipos deben ser diferentes.

¿Cuál es el objetivo de la clase de tipo MonadPlus ?

MonadPlus , como Alternative , es un fortalecimiento de Monoid , pero con respecto a Monad lugar de Applicative . Según Edward Kmett en su respuesta a la pregunta "Distinción entre clases de tipos MonadPlus , Alternative y Monoid ?" , MonadPlus también es más fuerte que Alternative : la ley empty <*> a , por ejemplo, no implica que el empty >>= f . AndrewC proporciona dos ejemplos de esto: Maybe y its dual. El problema se complica por el hecho de que hay dos posibles conjuntos de leyes para MonadPlus . Se acepta universalmente que se supone que MonadPlus forma un monoide con mplus y mempty , y se supone que mempty >>= f = mempty ley del cero izquierdo , mempty >>= f = mempty . Sin embargo, algunas MonadPlus ses satisfacen la distribución izquierda , mplus ab >>= f = mplus (a >>= f) (b >>= f) ; y otros satisfacen la captura izquierda , mplus (return a) b = return a . (Nótese que la distribución / cero izquierda para MonadPlus es análoga a la distribución / absorción correcta para Alternative ; (<*>) es más análoga a (=<<) que (>>=) .) La distribución izquierda es probablemente "mejor", por lo cualquier instancia de MonadPlus que satisfaga la captura de la izquierda, como Maybe , es una Alternative pero no el primer tipo de MonadPlus . Y como la pesca de la izquierda se basa en el pedido, puede imaginarse un envoltorio de tipo nuevo para Maybe cuya instancia Alternative sea correcta, en lugar de inclinada a la izquierda : a <|> Just b = Just b . Esto no satisfará la distribución izquierda ni la captura izquierda, pero será una Alternative perfectamente válida.

Sin embargo, dado que cualquier tipo que sea un MonadPlus debe tener su instancia coincidente con su instancia Alternative (creo que esto se requiere de la misma manera que se requiere que ap y (<*>) sean iguales para las Monad que son aplicables. ), podrías imaginarte definiendo la clase MonadPlus como

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

La clase no necesita declarar nuevas funciones; es solo una promesa sobre las leyes obedecidas por empty y (<|>) para el tipo dado. Esta técnica de diseño no se usa en las bibliotecas estándar de Haskell, pero se usa en algunos paquetes de mentalidad matemática para propósitos similares; por ejemplo, el paquete de lattices usa para expresar la idea de que una lattice es simplemente una semilícula de unión y una semilínea de reunión sobre el mismo tipo que están unidas por leyes de absorción.

La razón por la que no se puede hacer lo mismo con Alternative , incluso si se quería garantizar que Alternative y Monoid siempre coincidieran, se debe a la falta de coincidencia. La declaración de clase deseada tendría la forma

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

pero (como se menciona arriba) ni siquiera GHC Haskell soporta restricciones cuantificadas.

Además, tenga en cuenta que tener Alternative como una superclase de MonadPlus requeriría que Applicative sea ​​una superclase de Monad , así que buena suerte para que eso suceda. Si se encuentra con ese problema, siempre existe el tipo WrappedMonad WrappedMonad, que convierte cualquier Monad en un Applicative de la manera obvia; hay una instance MonadPlus m => Alternative (WrappedMonad m) where ... que hace exactamente lo que esperas.

Answer 4

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 strict 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. Ejemplos:

• 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. See also this answer .

_{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}

Answer 5

import Data.Monoid
import Control.Applicative

Vamos a rastrear a través de un ejemplo de cómo Monoid y Alternative interactúan con el functor Maybe y el functor ZipList , pero comencemos desde cero, en parte para tener nuevas definiciones en nuestras mentes, en parte para dejar de cambiar pestañas a bits de hackage todo el tiempo , pero sobre todo para que pueda ejecutar este ghci pasado para corregir mis errores tipográficos!

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

Aquí está el clon Maybe:

data Perhaps a = Yes a | No  deriving (Eq, Show)

instance Functor Perhaps where
   fmap f (Yes a) = Yes (f a)
   fmap f No      = No

instance Applicative Perhaps where
   pure a = Yes a
   No    <*> _     = No
   _     <*> No    = No
   Yes f <*> Yes x = Yes (f x)

y ahora 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

Estructura 1: elementos de combinación: Monoid

Tal vez clonar

Primero veamos Perhaps String . Hay dos formas de combinarlos. Primero concatenación

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

La concatenación funciona inherentemente en el nivel String, no realmente en el nivel Maybe, al tratar No como si fuera Yes [] . Es igual a liftA2 (++) . Es sensato y útil, pero tal vez podríamos generalizar de usar ++ a usar cualquier forma de combinación, ¡cualquier Monoid entonces!

(<++>) :: 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

Esta estructura monoide para Perhaps intenta trabajar tanto como sea posible en a nivel. Observe la restricción de Monoid a , diciéndonos que estamos usando la estructura desde a nivel. Esta no es una estructura Alternativa, es una estructura Monoide derivada (levantada).

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

Aquí utilicé la estructura de los datos para agregar estructura a todo el asunto. Si estuviera combinando Set s, podría agregar un contexto Ord a lugar.

ZipList clone

Entonces, ¿cómo debemos combinar elementos con zipList? ¿A qué deberían ir estos zip si los estamos combinando?

   Zip ["HELLO","MUM","HOW","ARE","YOU?"] 
<> Zip ["this", "is", "fun"]
=  Zip ["HELLO" ? "this",   "MUM" ? "is",   "HOW" ? "fun"]

mempty = ["","","","",..]   -- sensible zero element for zipping with ?

Pero, ¿para qué deberíamos usar ? . Yo digo que la única opción sensata aquí es ++ . En realidad, para listas, (<>) = (++)

   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

Pero, ¿para qué podemos usar ? Digo que estamos destinados a combinar elementos, por lo que deberíamos usar de nuevo el operador de combinación de elementos 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

Esta es la única forma sensata de combinar los elementos usando un zip, por lo que es la única instancia de monoid sensible.

Curiosamente, eso no funciona para el ejemplo Maybe anterior, porque Haskell no sabe cómo combinar Int s - ¿debería usar + o * ? Para obtener una instancia de Monoid en datos numéricos, envuélvalos en Sum o Product para indicarle qué monoid usar.

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]

Punto clave

Observe el hecho de que el tipo en un Monoid tiene kind * es exactamente lo que nos permite poner el contexto de Monoid a aquí - también podríamos agregar Eq a u Ord a . En un Monoid, los elementos crudos importan. Una instancia de Monoid está diseñada para permitirle manipular y combinar los datos dentro de la estructura.

Estructura 2: elección de nivel superior: alternativa

Un operador de elección es similar, pero también diferente.

Tal vez clonar

(<||>) :: Perhaps String -> Perhaps String -> Perhaps String
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  

Aquí no hay concatenación , no usamos ++ en absoluto, esta combinación funciona solo en el nivel Perhaps , así que cambiemos la firma de tipo a

(<||>) :: 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  

Tenga en cuenta que no hay restricciones: no estamos utilizando la estructura del nivel a, solo la estructura en el nivel Perhaps . Esta es una estructura alternativa.

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

ZipList clone

¿Cómo deberíamos elegir entre dos ziplists?

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

Sería muy tentador usar <|> en los elementos, pero no podemos porque el tipo de elementos no está disponible para nosotros. Comencemos con el empty . No puede usar un elemento porque no conocemos el tipo de elementos cuando definimos una Alternativa, por lo que tiene que ser Zip [] . Necesitamos que sea una identidad izquierda (y preferiblemente derecha) para <|> , entonces

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

Hay dos opciones sensatas para Zip [1,3,4] <|> Zip [10,20,30,40] :

1. Zip [1,3,4] porque es el primero, consistente con Maybe
2. Zip [10,20,30,40] porque es más largo, consistente con el descarte de Zip []

Bueno, eso es fácil de decidir: dado que pure x = Zip (repeat x) , ambas listas pueden ser infinitas, por lo que compararlas para la longitud puede que nunca terminen, por lo que tiene que elegir la primera. Por lo tanto, la única instancia alternativa sensata es:

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

Esta es la única alternativa sensata que podríamos haber definido. Observe cuán diferente es de la instancia de Monoid, porque no podíamos meternos con los elementos, ni siquiera podíamos mirarlos.

Punto clave

Tenga en cuenta que debido a que Alternative toma un constructor de tipo * -> * no hay forma posible de agregar un Ord a o Eq a o Monoid a contexto. No se permite que una alternativa use información sobre los datos dentro de la estructura. No puede, no importa cuánto le gustaría, hacer algo con los datos, excepto posiblemente tirarlo.

Punto clave: ¿Cuál es la diferencia entre Alternativo y Monoide?

No mucho, ambos son monoides, pero para resumir las dos últimas secciones:

Monoid * instancias Monoid * hacen posible combinar datos internos. Alternative (* -> *) instancias Alternative (* -> *) hacen imposible. Monoid proporciona flexibilidad, Alternative proporciona garantías. Los tipos * y (* -> *) son los principales impulsores de esta diferencia. Tenerlos a ambos te permite usar ambos tipos de operaciones.

Esto es lo correcto, y nuestros dos sabores son apropiados. La instancia de Monoid para Perhaps String representa reunir todos los caracteres, la instancia alternativa representa una elección entre cadenas.

No hay nada de malo en la instancia de Monoid para Maybe: está haciendo su trabajo, combinando datos.
No hay nada de malo en la instancia alternativa para Maybe: está haciendo su trabajo, eligiendo entre cosas.

La instancia de Monoid para Zip combina sus elementos. La instancia alternativa para Zip está obligada a elegir una de las listas, la primera no vacía.

Es bueno poder hacer ambas cosas.

¿Para qué sirve el contexto aplicativo?

Hay alguna interacción entre elegir y aplicar. Vea las leyes de Antal SZ en su pregunta o en medio de su respuesta aquí.

Desde un punto de vista práctico, es útil porque Alternativa es algo que se usa para elegir algunos Funcionadores Aplicativos. La funcionalidad se estaba utilizando para los solicitantes, por lo que se inventó una clase de interfaz general. Applicative Functors are good for representing computations that produce values (IO, Parser, Input UI element,...) and some of them have to handle failure - Alternative is needed.

Why does Alternative have empty ?

why does Alternative need an empty method/member? I may be wrong, but it seems to not be used at all ... at least in the code I could find. 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 distribution 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 ++ .