Confuso pelo significado da class de tipo ‘Alternativa’ e sua relação com outras classs de tipos

Eu tenho passado pela Typeclassopedia para aprender as classs de tipos. Eu estou preso entendendo Alternative (e MonadPlus , para esse assunto).

Os problemas que estou tendo:

  • o ‘pedia diz que’ a class de tipo Alternativa é para functores Aplicativos que também possuem uma estrutura monóide ‘. Eu não entendo isso – a alternativa não significa algo totalmente diferente do Monoid? Ou seja, eu entendi o ponto da class de tipos Alternativa como escolher entre duas coisas, enquanto eu entendia Monoids como sendo sobre combinar coisas.

  • Por que a Alternative precisa de um método / membro empty ? Eu posso estar errado, mas parece não ser usado … pelo menos no código que pude encontrar. E parece que não se encheckbox no tema da aula – se eu tenho duas coisas e preciso escolher uma, para que preciso de um ‘vazio’?

  • Por que a class de tipo Alternative precisa de uma restrição Applicative, e por que ela precisa de um tipo de * -> * ? Por que não apenas ter :: a -> a -> a ? Todas as instâncias ainda podem ser implementadas da mesma maneira … Eu acho (não tenho certeza). Qual o valor que o Monoid não oferece?

  • Qual é o objective da class de tipo MonadPlus ? Não posso desbloquear toda a sua bondade usando apenas algo como uma Monad e uma Alternative ? Por que não apenas abandoná-lo? (Tenho certeza que estou errado, mas não tenho contraexemplos)

Espero que todas essas perguntas sejam coerentes …!


Atualização de recompensa: A resposta de @ Antal é um ótimo começo, mas o Q3 ainda está aberto: o que a Alternative fornece que o Monoid não oferece? Acho essa resposta insatisfatória, uma vez que falta exemplos concretos e uma discussão específica de como a superioridade da Alternativa a distingue da Monoid.

Se é para combinar efeitos do aplicativo com o comportamento do Monoid, porque não apenas:

 liftA2 mappend 

Isso é ainda mais confuso para mim porque muitas instâncias Monoid são exatamente iguais às instâncias Alternativas.

É por isso que estou procurando exemplos específicos que mostram por que a Alternative é necessária e como é diferente – ou significa algo diferente – da Monoid.

Para começar, deixe-me oferecer respostas curtas a cada uma dessas perguntas. Em seguida, expandirei cada uma delas em uma resposta mais detalhada, mas essas curtas ajudarão a navegar nelas.

  1. Não, Alternative e Monoid não significam coisas diferentes; Alternative é para tipos que possuem a estrutura tanto de Applicative quanto de Monoid . “Picking” e “combinando” são duas intuições diferentes para o mesmo conceito mais amplo.

  2. Alternative contém tanto o empty quanto o <|> porque os projetistas acharam que isso seria útil, e porque isso dá origem a um monóide. Em termos de picking, empty corresponde a fazer uma escolha impossível.

  3. Precisamos de Alternative e Monoid porque o primeiro obedece (ou deveria) mais leis do que o segundo; essas leis relacionam a estrutura monoidal e aplicativa do construtor de tipos. Além disso, Alternative não pode depender do tipo interno, enquanto Monoid pode.

  4. MonadPlus é um pouco mais forte que o Alternative , pois deve obedecer a mais leis; essas leis relacionam a estrutura monoidal à estrutura monádica, além da estrutura aplicativa. Se você tiver instâncias de ambos, eles devem coincidir.


Alternative não significa algo totalmente diferente do Monoid ?

Na verdade não! Parte da razão para sua confusão é que a class Haskell Monoid usa alguns nomes bem ruins (bem, insuficientemente gerais). É assim que um matemático definiria um monóide (sendo bem explícito):

Definição. Um monóide é um conjunto M equipado com um elemento distinto εM e um operador binário ·: M × MM , indicado por justaposição, de modo que as seguintes duas condições mantenham:

  1. ε é a identidade: para todo mM , m ε = ε m = m .
  2. · É associativo: para todo m ₁, m ₂, mM , ( mm ₂) m ₃ = m ₁ ( mm ₃).

É isso aí. Em Haskell, ε é escrito como mempty e é grafado mappend (ou, atualmente, <> ), e o conjunto M é o tipo M na instance Monoid M where ...

Olhando para essa definição, vemos que ela não diz nada sobre “combinar” (ou sobre “escolher”, para esse assunto). Diz coisas sobre · e sobre ε , mas é isso. Agora, é certamente verdade que combinar as coisas funciona bem com esta estrutura: ε corresponde a não ter nada, e mm ₂ diz que se eu glom m ₁ e m together s coisas juntas, eu posso conseguir uma coisa nova contendo todas as suas coisas. Mas aqui está uma intuição alternativa: ε corresponde a nenhuma escolha, e mm ₂ corresponde a uma escolha entre m ₁ e m ₂. Esta é a intuição de “escolha”. Note que ambos obedecem às leis monóides:

  1. Não ter absolutamente nada e não ter escolha é a identidade.
    • Se eu não tenho nenhuma coisa e glom junto com algumas coisas, eu acabo com a mesma coisa novamente.
    • Se eu tiver uma escolha entre nenhuma escolha (algo impossível) e alguma outra escolha, eu tenho que escolher a outra (possível) escolha.
  2. As colecções de glomming em conjunto e a escolha são ambas associativas.
    • Se eu tiver três collections de coisas, não importa se eu fotografar as duas primeiras juntas e depois a terceira, ou as duas últimas juntas e depois a primeira; De qualquer forma, acabo com a mesma coleção glommed total.
    • Se eu tiver uma escolha entre três coisas, não importa se eu (a) escolho primeiro entre primeiro ou segundo e terceiro e depois, se preciso, entre primeiro e segundo, ou (b) primeiro escolho entre primeiro e segundo ou terceiro e depois, se preciso, entre segundo e terceiro. De qualquer forma, posso escolher o que quero.

(Nota: eu estou jogando rápido e solto aqui; é por isso que é intuição. Por exemplo, é importante lembrar que · não precisa ser comutativo, o que o acima cita: é perfeitamente possível que mmmm ₁ .)

Eis que ambos os tipos de coisas (e muitos outros – está multiplicando números realmente “combinando” ou “escolhendo”?) Obedecem às mesmas regras. Ter uma intuição é importante para desenvolver a compreensão, mas são as regras e definições que determinam o que realmente está acontecendo.

E a melhor parte é que essas duas intuições podem ser interpretadas pela mesma operadora! Seja M algum conjunto de conjuntos (não um conjunto de todos os conjuntos!) Contendo o conjunto vazio, seja ε o conjunto vazio ∅ e seja · definido como união ∪. É fácil ver que ∅ é uma identidade para ∪ e que ∪ é associativo, então podemos concluir que ( M , ∅, ∪) é um monóide. Agora:

  1. Se pensarmos nos conjuntos como sendo collections de coisas, então corresponderemos a reuni-los para obter mais coisas – a intuição de “combinação”.
  2. Se pensarmos nos conjuntos como representando ações possíveis, então ∪ corresponde a aumentar o seu conjunto de ações possíveis para escolher – a intuição de “escolha”.

E isso é exatamente o que está acontecendo com [] em Haskell: [a] é um Monoid para todos os a , e [] como um functor (e mônada) aplicativo é usado para representar o não-determinismo. Ambas as intuições de combinar e escolher coincidem no mesmo tipo: mempty = empty = [] e mappend = (<|>) = (++) .

Portanto, a class Alternative está ali apenas para representar objects que (a) são functores aplicativos e (b) quando instanciados em um tipo, possuem um valor e uma function binária neles que seguem algumas regras. Quais regras? O monóide governa. Por quê? Porque acaba sendo útil 🙂


Por que a Alternative precisa de um método / membro vazio?

Bem, a resposta sarcástica é “porque Alternative representa uma estrutura monóide”. Mas a verdadeira questão é: por que uma estrutura monóide? Por que não apenas um semigrupo, um monóide sem ε ? Uma resposta é afirmar que os monoids são apenas mais úteis. Eu acho que muitas pessoas (mas talvez não Edward Kmett ) concordariam com isso; quase o tempo todo, se você tiver um sensible (<|>) / mappend / ·, será capaz de definir um sensible empty / mempty / ε . Por outro lado, ter a generalidade extra é bom, já que permite colocar mais coisas sob o guarda-chuva.

Você também quer saber como isso se encheckbox com a intuição de “escolha”. Tendo em mente que, em certo sentido, a resposta certa é “saber quando abandonar a intuição ‘escolhendo’”, acho que você pode unificar os dois. Considere [] , o functor aplicativo para o não-determinismo. Se eu combinar dois valores do tipo [a] com (<|>) , isso corresponde a escolher não deterministicamente uma ação da esquerda ou uma ação da direita. Mas às vezes, você não terá ações possíveis de um lado – e tudo bem. Da mesma forma, se considerarmos analisadores, (<|>) representa um analisador que analisa o que está à esquerda ou o que está à direita (“escolhe”). E se você tem um analisador que sempre falha, isso acaba sendo uma identidade: se você escolher, você imediatamente rejeita essa escolha e tenta a outra.

Tudo isso dito, lembre- se que seria perfeitamente possível ter uma class quase como Alternative , mas sem empty . Isso seria perfeitamente válido – poderia até ser uma superclass da Alternative – mas não é o que Haskell fez. Presumivelmente, isso é um palpite sobre o que é útil.


Por que a class de tipo Alternative precisa de uma restrição Applicative e por que ela precisa de um tipo de * -> * ? … Por que não apenas [usar] liftA2 mappend ?

Bem, vamos considerar cada uma dessas três mudanças propostas: livrar-se da restrição Applicative para Alternative ; mudando o tipo de argumento da Alternative ; e usando liftA2 mappend vez de <|> e pure mempty vez de empty . Vamos ver essa terceira mudança primeiro, já que é a mais diferente. Suponha que nos livramos da Alternative inteiramente e substituímos a class por duas funções simples:

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

Poderíamos até manter as definições de some e many . E isso nos dá uma estrutura monóide, é verdade. Mas parece que nos dá a errada. Deve Just fst >|< Just snd falhar, desde (a,a) -> a não é uma instância do Monoid ? Não, mas é a isso que o código acima resultaria. A instância monóide que queremos é aquela que é agnóstico de tipo interno (para usar a terminologia de Matthew Farkas-Dyck em uma discussão de haskell-cafe muito relacionada que faz algumas perguntas muito semelhantes); Alternative estrutura Alternative é sobre um monóide determinado pela estrutura de f , não a estrutura do argumento de f .

Agora que achamos que queremos deixar a Alternative como uma espécie de class de tipos, vamos examinar as duas formas propostas de alterá-la. Se mudarmos o tipo, temos que nos livrar da restrição de Applicative ; Applicative só fala sobre coisas do tipo * -> * , e por isso não há como se referir a ele. Isso deixa duas mudanças possíveis; a primeira mudança, menor, é livrar-se da restrição de Aplicabilidade, mas deixar o tipo em paz:

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

A outra mudança, maior, é livrar-se da restrição Applicative e mudar o tipo:

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

>) :: a -> a -> a

Em ambos os casos, temos que nos livrar de some / many , mas tudo bem; podemos defini-las como funções autônomas com o tipo (Applicative f, Alternative' f) => fa -> f [a] ou (Applicative f, Alternative'' (f [a])) => fa -> f [a] .

Agora, no segundo caso, onde mudamos o tipo de variável type, vemos que nossa class é exatamente igual a Monoid (ou, se você ainda quer remover empty'' , Semigroup ), então não há vantagem em ter uma class separada. E, de fato, mesmo se deixarmos a variável do tipo sozinhos, mas removermos a restrição Applicative , a Alternative se tornará forall a. Monoid (fa) forall a. Monoid (fa) , embora não possamos escrever essas restrições quantificadas em Haskell, nem mesmo com todas as extensões extravagantes do GHC. (Observe que isso expressa o agnosticismo do tipo interno mencionado acima.) Assim, se podemos fazer uma dessas mudanças, então não temos razão para manter a Alternative (exceto por sermos capazes de expressar essa restrição quantificada, mas isso dificilmente parece convincente). ).

Então a questão se resume a “existe uma relação entre as partes Alternative e as Partes Applicative de um f que é uma instância de ambos?” E enquanto não há nada na documentação, eu vou tomar uma posição e dizer sim – ou, pelo menos, deveria haver. Eu acho que a Alternative deve obedecer a algumas leis relacionadas ao Applicative (além das leis monoidais); em particular, acho que essas leis são algo como

  1. Distribuitividade direita (de <*> ): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
  2. Absorção correta (para <*> ): empty <*> a = empty
  3. Distribuitividade esquerda (de fmap ): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
  4. Absorção Esquerda (para fmap ): f <$> empty = empty

Essas leis parecem ser verdadeiras para [] e Maybe , e (fingindo que sua instância MonadPlus é uma instância Alternative ) IO , mas eu não fiz nenhuma prova ou testes exaustivos. (Por exemplo, eu originalmente pensava que distributividade esquerda era para <*> , mas isso “executa os efeitos” na ordem errada para [] .) Por analogia, no entanto, é verdade que se espera que o MonadPlus obedeça leis semelhantes (embora aparentemente haja alguma ambiguidade sobre qual ). Eu queria originalmente reivindicar uma terceira lei, que parece natural:

  • Absorção esquerda (para <*> ): a <*> empty = empty

No entanto, embora eu acredite [] e Maybe obedeça a esta lei, IO não, e eu acho (por razões que se tornarão aparentes nos próximos parágrafos) é melhor não exigir isso.

E, de fato, parece que Edward Kmett tem alguns slides onde ele defende uma visão similar; para entrar nisso, precisaremos de uma breve digressão envolvendo algum jargão mais matemático. O slide final, “Eu quero mais estrutura”, diz que “Um monóide é para um aplicativo como um seminário de direita é uma alternativa”, e “Se você jogar fora o argumento de um candidato, você ganha um monóide, se você jogar afastado o argumento de uma alternativa você obtém um RightSemiNearRing. ”

Seminarrings corretos? “Como os seminários certos entraram nisso?” Eu ouço você chorar. Bem,

Definição. Um direito quase semiarring (também seminarring direito , mas o primeiro parece ser usado mais no Google) é um quádruplo ( R , +, ·, 0), onde ( R , +, 0) é um monóide, ( R , ·) é um semigrupo e as duas condições a seguir são válidas:

  1. · É distribuidora direita sobre +: para todos os r , s , tR , ( s + t ) r = sr + tr .
  2. 0 é absorvente pela direita para:: para todo rR , 0 r = 0.

Uma esquerda quase semiar é definida analogamente.

Agora, isso não funciona, porque <*> não é realmente associativo ou um operador binário – os tipos não correspondem. Eu acho que isso é o que Edward Kmett está chegando quando ele fala sobre “jogar fora” o argumento. Outra opção pode ser dizer (não tenho certeza se isso é certo) que nós realmente queremos ( fa , <|> , <*> , empty ) para formar um direito quase semicondicionado , onde o sufixo “-oid” indica que os operadores binários só podem ser aplicados a pares específicos de elementos (à la groupoids ). E também gostaríamos de dizer que ( fa , <|> , <$> , empty ) era um quase-semideídeide esquerdo, embora isso pudesse ser concebido da combinação das leis aplicáveis ​​e da estrutura quase semerróide. Mas agora estou passando por cima da minha cabeça, e isso não é profundamente relevante de qualquer maneira.

De qualquer forma, essas leis, sendo mais fortes do que as leis monóides, significam que instâncias Monoid perfeitamente válidas se tornariam inválidas. Instâncias Alternative . Existem (pelo menos) dois exemplos disso na biblioteca padrão: Monoid a => (a,) e Maybe . Vamos olhar para cada um deles rapidamente.

Dados quaisquer dois monóides, seu produto é um monóide; conseqüentemente, as tuplas podem ser feitas uma instância do Monoid da maneira óbvia (reformatando a fonte do pacote base ):

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

Da mesma forma, podemos fazer tuplas cujo primeiro componente é um elemento de um monóide em uma instância de Applicative , acumulando os elementos monoidais (reformatando a fonte do pacote base ):

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

Entretanto, as tuplas não são um exemplo de Alternative , porque elas não podem ser – a estrutura monoidal sobre Monoid a => (a,b) não está presente para todos os tipos b , e a estrutura monoidal de Alternative deve ser interna. digite agnóstico. Não apenas deve ser uma mônada, para poder expressar (f <> g) <*> a , precisamos usar a instância Monoid para funções, que é para funções da forma Monoid b => a -> b . E mesmo no caso em que temos toda a estrutura monoidal necessária, ela viola todas as quatro leis Alternative . Para ver isto, deixe ssf n = (Sum n, (<> Sum n)) e deixe ssn = (Sum n, Sum n) . Então, escrevendo (<>) para mappend , obtemos os seguintes resultados (que podem ser verificados no GHCi, com a anotação de tipo ocasional):

  1. Distribuição certa:
    • (ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
    • (ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
  2. Absorção direita:
    • mempty <*> ssn 1 = (Sum 1, Sum 0)
    • mempty = (Sum 0, Sum 0)
  3. Distribuidora esquerda:
    • (<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
    • ((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
  4. Absorção esquerda:
    • (<> Sum 1) <$> mempty = (Sum 0, Sum 1)
    • mempty = (Sum 1, Sum 1)

Em seguida, considere Maybe . Tal como está, as instâncias Monoid e Alternative Monoid discordam . (Embora a discussão haskell-cafe que mencionei no início desta seção proponha mudar isso, existe um Option newtype do pacote semigroups que produziria o mesmo efeito.) Como um Monoid , Maybe Monoid semigrupos em monoids usando Nothing como a identidade ; já que o pacote base não tem uma class semigroup, ele apenas eleva os monoids, e assim nós obtemos (reformatando a fonte do pacote 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 outro lado, como Alternative , Maybe represente a escolha priorizada com falha, e assim obtemos (novamente reformatando a fonte do pacote base ):

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

E acontece que somente este último satisfaz as leis Alternative . A instância Monoid falha menos que a de (,) ; obedece às leis com respeito a <*> , embora quase por acidente – vem do comportamento da única instância de Monoid para funções, que (como mencionado acima) levanta funções que retornam monoides no functor do leitor. Se você resolver isso (é tudo muito mecânico), você descobrirá que a distribuição correta e a absorção correta para <*> são Monoid instâncias Alternative e Monoid , assim como a absorção à esquerda para fmap . A distributividade esquerda para fmap é válida para a instância Alternative , da seguinte maneira:

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

No entanto, falha para a instância Monoid ; escrevendo (<>) para mappend , temos:

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

Agora, há uma advertência para este exemplo. Se você requerer apenas que as Alternative sejam compatíveis com <*> , e não com <$> , então Maybe esteja tudo bem. Os slides de Edward Kmett, mencionados acima, não fazem referência a <$> , mas acho que parece razoável exigir leis com relação a isso também; no entanto, não consigo encontrar nada para me apoiar nisso.

Assim, podemos concluir que ser uma Alternative é uma exigência mais forte do que ser um Monoid , e por isso requer uma class diferente. O exemplo mais puro disso seria um tipo com uma instância Monoid agnóstica de tipo Monoid e uma instância de Applicative que eram incompatíveis entre si; no entanto, não há nenhum desses tipos no pacote base e não consigo pensar em nenhum. (É possível que não exista, embora eu me surpreenda.) No entanto, esses exemplos gnósticos do tipo interno demonstram por que as duas classs de tipos devem ser diferentes.


Qual é o objective da class de tipo MonadPlus ?

MonadPlus , como o Alternative , é um fortalecimento do Monoid , mas com relação ao Monad vez do Applicative . De acordo com Edward Kmett em sua resposta à pergunta “Distinção entre typeclasss MonadPlus , Alternative e Monoid ?” , MonadPlus também é mais forte que Alternative : a lei empty <*> a , por exemplo, não implica que empty >>= f . AndrewC fornece dois exemplos disso: Maybe e seu dual. A questão é complicada pelo fato de que existem dois possíveis conjuntos de leis para o MonadPlus . É universalmente aceito que o MonadPlus deve formar um monóide com mplus e mempty , e deve satisfazer a lei do zero , mempty >>= f = mempty . No entanto, alguns MonadPlus ses satisfazem a distribuição à esquerda , mplus ab >>= f = mplus (a >>= f) (b >>= f) ; e outros satisfazem o catch esquerdo , mplus (return a) b = return a . (Note que left zero / distribution para MonadPlus são análogos a distributividade / absorção direita para Alternative ; (<*>) é mais análogo a (=<<) que (>>=) .) A distribuição esquerda é provavelmente “better”, então qualquer instância do MonadPlus que satisfaça o catch esquerdo, como o Maybe , é uma Alternative mas não o primeiro tipo do MonadPlus . E como o catch esquerdo depende da ordenação, você pode imaginar um wrapper newtype para Maybe cuja instância Alternative está certa - inclinada em vez de esquerda - inclinada: a <|> Just b = Just b . Isto não satisfará nem a distribuição à esquerda nem a captura à esquerda, mas será uma Alternative perfeitamente válida.

No entanto, desde que qualquer tipo que é um MonadPlus deve ter sua instância coincidir com sua instância Alternative (eu acredito que isso é necessário da mesma forma que é necessário que ap e (<*>) são iguais para Monad s que são Applicative s ), você poderia imaginar definir a class MonadPlus como

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

A class não precisa declarar novas funções; é apenas uma promise sobre as leis obedecidas por empty e (<|>) para o tipo dado. Essa técnica de design não é usada nas bibliotecas padrão do Haskell, mas é usada em alguns pacotes mais matematicamente para fins semelhantes; por exemplo, o pacote de reticulados usa-o para expressar a idéia de que uma rede é apenas um semilattice de junit e um semilattice de reunião sobre o mesmo tipo que estão ligados por leis de absorção.

A razão pela qual você não pode fazer o mesmo pela Alternative , mesmo se você quisesse garantir que Alternative e Monoid sempre coincidissem, é por causa da incompatibilidade de tipo. A declaração de class desejada teria o formulário

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

mas (como mencionado acima) nem mesmo GHC Haskell suporta restrições quantificadas.

Além disso, note que ter a Alternative como uma superclass do MonadPlus exigiria que o Applicative fosse uma superclass da Monad , então boa sorte para que isso aconteça. Se você se deparar com esse problema, há sempre o WrappedMonad WrappedMonad, que transforma qualquer Monad em um Applicative da maneira óbvia; há uma instance MonadPlus m => Alternative (WrappedMonad m) where ... que faz exatamente o que você espera.

 import Data.Monoid import Control.Applicative 

Vamos traçar um exemplo de como Monoid e Alternative interagem com o functor Maybe e o functor ZipList , mas vamos começar do zero, em parte para obter todas as definições novas em nossas mentes, em parte para parar de trocar as abas por bits de hackage o tempo todo , mas principalmente para que eu possa executar este ghci passado para corrigir meus erros!

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

Aqui está o clone de Maybe:

 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) 

e agora 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 

Estrutura 1: combinando elementos: Monoid

Talvez clone

Primeiro, vamos dar uma olhada em Perhaps String . Existem duas maneiras de combiná-las. Primeiramente concatenação

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

A concatenação funciona inerentemente no nível String, não no nível Talvez, tratando No como se fosse Yes [] . É igual a liftA2 (++) . É sensato e útil, mas talvez pudéssemos generalizar desde o uso do ++ até o uso de qualquer forma de combinação – qualquer Monoid então!

 (<++>) :: 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 estrutura monóide para Perhaps tenta trabalhar tanto quanto possível no nível a. Observe o Monoid a restrição, nos dizendo que estamos usando a estrutura do nível a. Esta não é uma estrutura alternativa, é uma estrutura monóide derivada (levantada).

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

Aqui eu usei a estrutura dos dados para adicionar estrutura à coisa toda. Se eu estivesse combinando Set s, seria possível adicionar Ord a contexto Ord a vez disso.

Clone da ZipList

Então, como devemos combinar elementos com um zipList? O que estes devem fazer se os combinarmos?

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

Mas o que devemos usar ? . Eu digo que a única escolha sensata aqui é ++ . Na verdade, 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 

Mas o que podemos usar ? Eu digo que estamos combinando elementos, então devemos usar o operador de combinação de elementos da Monoid novamente: <> .

 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 é a única maneira sensata de combinar os elementos usando um zip – então é a única instância monóide sensata.

Curiosamente, isso não funciona para o exemplo Maybe acima, porque Haskell não sabe como combinar Int s – deve usar + ou * ? Para obter uma ocorrência Monoid em dados numéricos, você os envolve em Sum ou Product para informar qual monóide 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] 

Ponto chave

Observe o fato de que o tipo em um Monoid tem kind * é exatamente o que nos permite colocar aqui o Monoid a – podemos também adicionar Eq a ou Ord a . Em um monóide, os elementos brutos importam. Uma instância Monoid é projetada para permitir que você manipule e combine os dados dentro da estrutura.

Estrutura 2: escolha de nível superior: alternativa

Um operador de escolha é semelhante, mas também diferente.

Talvez clone

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

Aqui não há concatenação – nós não usamos o ++ – essa combinação funciona puramente no nível Perhaps , então vamos mudar a assinatura do tipo para

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

Observe que não há restrição – não estamos usando a estrutura do nível a, apenas estruturamos no nível Perhaps . Esta é uma estrutura alternativa.

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

Clone da ZipList

Como devemos escolher entre dois ziplistas?

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

Seria muito tentador usar <|> os elementos, mas não podemos porque o tipo de elementos não está disponível para nós. Vamos começar com o empty . Não é possível usar um elemento porque não sabemos o tipo de elementos ao definir uma alternativa, por isso tem que ser Zip [] . Precisamos que seja uma identidade esquerda (e de preferência correta) para <|> ,

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

Há duas escolhas sensatas para Zip [1,3,4] <|> Zip [10,20,30,40] :

  1. Zip [1,3,4] porque é o primeiro – consistente com Talvez
  2. Zip [10,20,30,40] porque é o mais longo – consistente com o Zip [] sendo descartado

Bem, isso é fácil de decidir: como pure x = Zip (repeat x) , ambas as listas podem ser infinitas, então compará-las para comprimento nunca pode terminar, então tem que escolher a primeira. Assim, a única instância alternativa sensata é:

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

Esta é a única alternativa sensata que poderíamos ter definido. Note como é diferente da instância do Monoid, porque não conseguimos mexer com os elementos, nem conseguimos olhar para eles.

Ponto chave

Observe que, como o Alternative toma um construtor do tipo * -> * não é possível Monoid a contexto Ord a ou Eq a ou Monoid a . Uma alternativa não tem permissão para usar qualquer informação sobre os dados dentro da estrutura. Você não pode, não importa o quanto você gostaria, fazer qualquer coisa com os dados, exceto possivelmente jogá-los fora.

Ponto-chave: Qual é a diferença entre Alternativa e Monóide?

Não muito – ambos são monóides, mas para resumir as duas últimas seções:

Monoid * tornam possível combinar dados internos. Instâncias Alternative (* -> *) tornam isso impossível. Monoid fornece flexibilidade, Alternativa fornece garantias. Os tipos * e (* -> *) são os principais responsáveis ​​por essa diferença. Ter ambos permite que você use ambos os tipos de operações.

Esta é a coisa certa, e nossos dois sabores são adequados. A instância Monoid para Maybe Perhaps String representa unir todos os caracteres, a instância Alternative representa uma escolha entre Strings.

Não há nada de errado com a instância do Monoid para o Maybe – ele está fazendo seu trabalho, combinando dados.
Não há nada de errado com a instância Alternativa de Maybe – está fazendo seu trabalho, escolhendo entre as coisas.

A instância do Monoid para o Zip combina seus elementos. A instância alternativa do Zip é forçada a escolher uma das listas – a primeira não vazia.

É bom poder fazer as duas coisas.

Para que serve o contexto de aplicação?

Há alguma interação entre escolher e aplicar. Veja as leis de Antal SZ declaradas em sua pergunta ou no meio de sua resposta aqui.

De um ponto de vista prático, é útil porque Alternativa é algo que é usado por alguns candidatos a escolher. A funcionalidade estava sendo usada para o Applicatives, e assim uma class de interface geral foi inventada. Functores Aplicativos são bons para representar computações que produzem valores (IO, Parser, Input UI element, …) e alguns deles têm que lidar com falhas – Alternativas são necessárias.

Por que a alternativa tem 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 superclasss 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 ++ .

Resumo

  • 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. Nós temos

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

Opa! Nós temos

 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.


Então você tem isso. 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.

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. Exemplos:

  • 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. Veja também esta resposta .


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.