Rozróżnienie między typeklasami MonadPlus, Alternative i Monoid?

85

Średnia Biblioteka Haskell typeclasses MonadPlus, Alternativei Monoidkażdy zapewniają dwie metody z zasadniczo tą samą składnię:

  • Pusta wartość: mzero, empty, lub mempty.
  • Operator a -> a -> a, który łączy wartości w typeclass razem: mplus, <|>, lub mappend.

Wszystkie trzy określają te prawa, których powinny przestrzegać instancje:

mempty `mappend` x = x
x `mappend` mempty = x

Dlatego wydaje się, że wszystkie trzy typeklasy zapewniają te same metody.

( Alternativezawiera również somei many, ale ich domyślne definicje są zwykle wystarczające, więc nie są zbyt ważne w kontekście tego pytania).

Więc moje zapytanie brzmi: dlaczego te trzy niezwykle podobne klasy? Czy jest między nimi jakaś prawdziwa różnica, poza ich różnymi ograniczeniami dla nadklasy?

00dani
źródło
To dobre pytanie. W szczególności Applicativei MonadPluswydają się być dokładnie takie same (ograniczenia modulo nadklasy).
Peter,
1
Jest też ArrowZeroi ArrowPlusna strzały. Mój zakład: uczynić podpisy czystszymi (co sprawia, że ​​różne ograniczenia nadklasy prawdziwą różnicą).
Cat Plus Plus
2
@CatPlusPlus: no ArrowZeroi ArrowPlusmiej rodzaj * -> * -> *, co oznacza, że ​​możesz przekazać je dla typu strzałki raz dla funkcji, która musi ich używać dla wielu typów, aby użyć Monoid, musiałbyś wymagać wystąpienia Monoiddla każdego konkretnego tworzenie instancji i nie miałbyś gwarancji, że były obsługiwane w podobny sposób, instancje mogą być niepowiązane!
Edward KMETT,

Odpowiedzi:

122

MonadPlusi Monoidsłużą różnym celom.

A Monoidjest sparametryzowany względem rodzaju *.

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m

dzięki czemu można go utworzyć dla prawie każdego typu, dla którego istnieje oczywisty operator, który jest asocjacyjny i który ma jednostkę.

Jednak MonadPlusnie tylko określa, że ​​masz monoidalną strukturę, ale także, że ta struktura jest związana z tym, jak Monaddziała, i że ta struktura nie dba o wartość zawartą w monadzie, jest to (częściowo) wskazywane przez fakt to MonadPluswymaga pewnego argumentu * -> *.

class Monad m => MonadPlus m where
    mzero :: m a
    mplus :: m a -> m a -> m a

Oprócz praw monoidowych mamy dwa potencjalne zbiory praw, do których możemy się zastosować MonadPlus. Niestety społeczność nie zgadza się co do tego, czym powinny być.

Przynajmniej wiemy

mzero >>= k = mzero

ale istnieją dwa inne konkurujące ze sobą rozszerzenia, lewe (sic) prawo dystrybucji

mplus a b >>= k = mplus (a >>= k) (b >>= k)

i lewe prawo catch

mplus (return a) b = return a

Zatem każdy przypadek MonadPluspowinien spełniać jedno lub oba z tych dodatkowych praw.

Więc o co chodzi Alternative?

Applicativezostała zdefiniowana później Monadi logicznie należy do nadklasy Monad, ale głównie ze względu na różne naciski na projektantów w Haskell 98, nawet Functornie była superklasą Monadaż do 2015 roku. Teraz w końcu mamy Applicativenadklasę Monadw GHC (jeśli nie jeszcze w standardzie językowym.)

Skutecznie Alternativejest do Applicativetego, co MonadPlusjest Monad.

Za to dostaniemy

empty <*> m = empty

analogicznie do tego, co mamy MonadPlusi istnieją podobne właściwości dystrybucyjne i przechwytujące, z których przynajmniej jedną należy spełnić.

Niestety, nawet empty <*> m = emptyprawo jest zbyt mocnym roszczeniem. Na przykład nie sprawdza się w przypadku Backwards !

Kiedy patrzymy na MonadPlus, puste >> = f = puste prawo jest nam prawie narzucone. Pusta konstrukcja nie może zawierać żadnego „a”, aby wywołać funkcję f.

Jednak, ponieważ Applicativejest nie nadklasą Monadi Alternativeto nie nadklasą MonadPlus, możemy skończyć zdefiniowania obu instancji oddzielnie.

Co więcej, nawet gdyby Applicativebyła superklasą Monad, i tak potrzebowałbyś tej MonadPlusklasy, ponieważ nawet gdybyśmy byli posłuszni

empty <*> m = empty

to nie wystarczy, aby to udowodnić

empty >>= f = empty

Twierdzenie, że coś jest a, MonadPlusjest silniejsze niż twierdzenie, że jest Alternative.

Teraz umownie, MonadPlusi Alternativedla danego typu powinny się zgadzać, ale Monoidmoże być zupełnie inaczej.

Na przykład MonadPlusi Alternativedla Maybezrobić oczywistą rzecz:

instance MonadPlus Maybe where
    mzero = Nothing
    mplus (Just a) _  = Just a
    mplus _        mb = mb

ale Monoidinstancja podnosi półgrupę do Monoid. Niestety, ponieważ Semigroupw tym czasie w Haskell 98 nie istniała klasa, robi to, żądając Monoid, ale nie używając swojej jednostki. ಠ_ಠ

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    mappend (Just a) (Just b) = Just (mappend a b)
    mappend Nothing x = x
    mappend x Nothing = x
    mappend Nothing Nothing = Nothing

TL; DR MonadPlus jest twierdzeniem silniejszym niż Alternative, które z kolei jest twierdzeniem silniejszym niż Monoid, i chociaż wystąpienia MonadPlusi Alternativedla typu powinny być powiązane, Monoidmoże być (a czasami jest) czymś zupełnie innym.

Edward KMETT
źródło
2
Doskonała odpowiedź, jednak ostatnia definicja wydaje się błędna, nie satysfakcjonuje mempty `mappend` x ≡ x.
Vitus,
2
Świetna odpowiedź. Czy ktoś wie o (powszechnie używanym) typie, który ma różne MonadPlus i Alternativeimplementacje?
Peter
7
@EdwardKmett: Ta odpowiedź wydaje się sugerować, że może istnieć element, Monadktóry jest, Alternativeale nie MonadPlus. I zadał pytanie o znalezienie konkretnego przykładu tego; jeśli znasz jeden, chciałbym to zobaczyć.
Antal Spector-Zabusky
2
Czy możesz wyjaśnić lewe prawo catch dla monadplus? Najwyraźniej jest naruszony przez []; czy [] naprawdę powinien ignorować swój drugi argument, jeśli pierwszy nie jest pusty?
ben w
4
Dystrybucja lewostronna @benw jest prawdopodobnie rozsądniejszym prawem, ale w niektórych przypadkach nie obowiązuje. left catch to alternatywne prawo, które inne instancje zwykle popierają, ale które nie są obsługiwane przez większość innych. W rezultacie mamy naprawdę 2 w dużej mierze niezwiązane ze sobą zbiory praw wdrażane przez różne instancje, więc tak MonadPlusnaprawdę dwie klasy są przebrane za jedną, ponieważ większości ludzi to nie obchodzi.
Edward KMETT