Moim skromnym zdaniem odpowiedzi na słynne pytanie „Co to jest monada?” , zwłaszcza tych najczęściej głosowanych, spróbuj wyjaśnić, co to jest monada, bez wyraźnego wyjaśnienia, dlaczego monady są naprawdę potrzebne . Czy można je wyjaśnić jako rozwiązanie problemu?
366
Odpowiedzi:
Dlaczego potrzebujemy monad?
Mamy więc pierwszy duży problem. To jest program:
f(x) = 2 * x
g(x,y) = x / y
Jak możemy powiedzieć, co należy najpierw wykonać ? Jak możemy utworzyć uporządkowaną sekwencję funkcji (tj. Program ), używając tylko funkcji ?
Rozwiązanie: komponuj funkcje . Jeśli chcesz najpierw
g
, a następnief
, po prostu napiszf(g(x,y))
. W ten sposób, „program” jest funkcją, a także:main = f(g(x,y))
. Dobrze, ale ...Więcej problemów: niektóre funkcje mogą zawieść (tzn.
g(2,0)
Podzielić przez 0). W FP nie mamy „wyjątków” (wyjątek nie jest funkcją). Jak to rozwiązujemy?Rozwiązanie: Pozwólmy funkcjom zwrócić dwie rzeczy : zamiast mieć
g : Real,Real -> Real
(funkcja z dwóch rzeczywistych w rzeczywistą), pozwólmyg : Real,Real -> Real | Nothing
(funkcja z dwóch rzeczywistych w rzeczywistą lub rzeczywistą).Ale funkcje powinny (mówiąc prościej) zwracać tylko jedną rzecz .
Rozwiązanie: stwórzmy nowy typ danych, które mają zostać zwrócone, „ typ boksu ”, który może zawierać rzeczywisty lub po prostu nic. Dlatego możemy mieć
g : Real,Real -> Maybe Real
. Dobrze, ale ...Co się teraz stanie
f(g(x,y))
?f
nie jest gotowy do spożyciaMaybe Real
. I nie chcemy zmieniać każdej funkcji, z którą możemy się połączyć,g
aby zużyćMaybe Real
.Rozwiązanie: skorzystajmy ze specjalnej funkcji do łączenia funkcji / łączenia / tworzenia / łączenia . W ten sposób możemy za kulisami dostosować wyjście jednej funkcji, aby zasilić następną.
W naszym przypadku:
g >>= f
(connect / komponowaćg
sięf
). Chcemy>>=
uzyskaćg
dane wyjściowe, sprawdzić je, a jeśliNothing
tak, to nie dzwońf
i nie wracajNothing
; lub wręcz przeciwnie, wyodrębnij pudełkoReal
i karmf
je nim. (Ten algorytm jest właśnie realizacja>>=
dlaMaybe
typu). Należy również pamiętać, że>>=
należy napisać tylko raz dla „typu boksu” (inne pole, inny algorytm dostosowujący).Powstaje wiele innych problemów, które można rozwiązać za pomocą tego samego wzorca: 1. Użyj „pudełka”, aby skodyfikować / zapisać różne znaczenia / wartości, i takie funkcje
g
zwracają te „wartości w pudełkach”. 2. Poproś kompozytora / linkera,g >>= f
aby pomógłg
podłączyć wyjście dof
wejścia, więc nie musimy gof
w ogóle zmieniać .Niezwykłe problemy, które można rozwiązać za pomocą tej techniki:
posiadające globalny stan, w którym każda funkcja w sekwencji funkcji („program”) może współdzielić: rozwiązanie
StateMonad
.Nie lubimy „nieczystych funkcji”: funkcji, które dają różne dane wyjściowe dla tego samego wejścia. Dlatego zaznaczmy te funkcje, aby zwróciły wartość oznaczoną / umieszczoną w ramce:
IO
monad.Całkowite szczęście!
źródło
IO
monada to tylko jeden problem na liścieIO
(punkt 7). Z drugiej stronyIO
pojawia się tylko raz i na końcu, więc nie rozumiem swojego „większego czasu na mówienie ... o IO”.Either
). Większość odpowiedzi dotyczy „Dlaczego potrzebujemy funktorów?”.g >>= f
który pomoże połączyćg
wyjście zf
wejściem, więc nie musimy gof
w ogóle zmieniać ”. to wcale nie jest w porządku . Przed, wf(g(x,y))
,f
może produkować cokolwiek. To może byćf:: Real -> String
. W przypadku „składu monadycznego” należy go zmienić, aby produkowaćMaybe String
, w przeciwnym razie typy nie będą pasować. Co więcej,>>=
sam nie pasuje !! To właśnie>=>
ta kompozycja nie robi>>=
. Zobacz dyskusję z dfeuer pod odpowiedzią Carla.Odpowiedź brzmi oczywiście „nie” . Jak w przypadku wszystkich abstrakcji, nie jest to konieczne.
Haskell nie potrzebuje abstrakcji monady. Nie jest konieczne wykonywanie IO w czystym języku. Ten
IO
typ sam sobie z tym radzi. Istniejący monadycznego desugaring zdo
bloków można zastąpić desugaring dobindIO
,returnIO
ifailIO
, jak określono wGHC.Base
module. (To nie jest udokumentowany moduł dotyczący hakowania, więc będę musiał wskazać jego źródło dla dokumentacji.) Więc nie, nie ma potrzeby abstrakcji monady.Więc jeśli nie jest potrzebny, dlaczego istnieje? Ponieważ stwierdzono, że wiele wzorów obliczeń tworzy struktury monadyczne. Abstrakcja struktury pozwala na pisanie kodu, który działa we wszystkich instancjach tej struktury. Mówiąc bardziej zwięźle - użyj kodu ponownie.
W językach funkcjonalnych najpotężniejszym narzędziem do ponownego wykorzystania kodu jest zestaw funkcji. Dobry stary
(.) :: (b -> c) -> (a -> b) -> (a -> c)
operator jest niezwykle potężny. Ułatwia pisanie drobnych funkcji i łączenie ich przy minimalnym nakładzie składniowym lub semantycznym.Ale zdarzają się przypadki, gdy typy nie działają całkiem dobrze. Co robisz, kiedy masz
foo :: (b -> Maybe c)
ibar :: (a -> Maybe b)
?foo . bar
nie sprawdza typu, ponieważb
iMaybe b
nie są tego samego typu.Ale ... to prawie racja. Chcesz trochę swobody. Chcesz być w stanie traktować to
Maybe b
tak, jakby to było w zasadzieb
. Jednak kiepskim pomysłem jest traktowanie ich jako tego samego typu. To mniej więcej to samo, co wskaźniki zerowe, które Tony Hoare nazwał błędem miliard dolarów . Jeśli więc nie możesz traktować ich jako tego samego typu, być może możesz znaleźć sposób na rozszerzenie mechanizmu kompozycji(.)
.W takim przypadku ważne jest, aby naprawdę zbadać leżącą u podstaw teorię
(.)
. Na szczęście ktoś już to dla nas zrobił. Okazuje się, że kombinacja(.)
iid
forma konstruktu matematycznego znanego jako kategoria . Istnieją jednak inne sposoby tworzenia kategorii. Na przykład kategoria Kleisli pozwala nieco rozszerzyć komponowane obiekty. Kategoria Kleisli dlaMaybe
składałaby się z(.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)
iid :: a -> Maybe a
. Oznacza to, że obiekty w kategorii rozszerzają się(->)
oMaybe
, więc(a -> b)
staje się(a -> Maybe b)
.I nagle rozszerzyliśmy moc kompozycji na rzeczy, na których tradycyjna
(.)
operacja nie działa. To jest źródło nowej mocy abstrakcji. Kategorie Kleisli działają z większą liczbą typów niż tylkoMaybe
. Działają z każdym typem, który może złożyć odpowiednią kategorię, przestrzegając praw kategorii.id . f
=f
f . id
=f
f . (g . h)
=(f . g) . h
Dopóki możesz udowodnić, że twój typ przestrzega tych trzech praw, możesz zmienić go w kategorię Kleisli. A o co w tym wszystkim chodzi? Okazuje się, że monady są dokładnie tym samym co kategorie Kleisli.
Monad
„sreturn
jest taki sam jak Kleisliid
.Monad
„s(>>=)
nie jest identyczna Kleisli(.)
, ale okazuje się, że bardzo łatwo pisać każdy pod względem drugiej. A prawa kategorii są takie same jak prawa monady, kiedy przekładasz je na różnice między(>>=)
i(.)
.Po co więc męczyć się tym wszystkim? Dlaczego
Monad
abstrakcja w języku? Jak wspomniałem powyżej, umożliwia ponowne użycie kodu. Umożliwia nawet ponowne użycie kodu w dwóch różnych wymiarach.Pierwszy wymiar ponownego użycia kodu pochodzi bezpośrednio z obecności abstrakcji. Możesz napisać kod, który działa we wszystkich przypadkach abstrakcji. Istnieje cały pakiet monad-loops składający się z pętli, które działają z dowolnym wystąpieniem
Monad
.Drugi wymiar jest pośredni, ale wynika z istnienia kompozycji. Kiedy kompozycja jest łatwa, naturalne jest pisanie kodu małymi fragmentami wielokrotnego użytku. W ten sam sposób
(.)
operator funkcji zachęca do pisania małych funkcji wielokrotnego użytku.Dlaczego więc istnieje abstrakcja? Ponieważ udowodniono, że jest to narzędzie, które umożliwia większą kompozycję kodu, co powoduje tworzenie kodu wielokrotnego użytku i zachęcanie do tworzenia kodu wielokrotnego użytku. Ponowne użycie kodu jest jednym ze świętych Graali programowania. Abstrakcja monady istnieje, ponieważ przybliża nas trochę do świętego Graala.
źródło
newtype Kleisli m a b = Kleisli (a -> m b)
. Kategorie Kleisli to funkcje, w których kategoryczny typ zwracany (b
w tym przypadku) jest argumentem dla konstruktora typum
. IffKleisli m
tworzy kategorię,m
jest Monadą.Kleisli m
wydaje się tworzyć kategorię, której obiekty są typami Haskella i takie, że strzałki oda
dob
są funkcjami oda
dom b
, zid = return
i(.) = (<=<)
. Czy to w porządku, czy mieszam różne poziomy rzeczy czy coś?a
ib
, ale nie są to proste funkcje. Są ozdobione dodatkowąm
wartością zwracaną przez funkcję.Benjamin Pierce powiedział w TAPL
Dlatego język wyposażony w potężny system pisma jest bardziej wyrazisty niż język źle napisany. Możesz myśleć o monadach w ten sam sposób.
Jako @Carl i sigfpe point możesz wyposażyć typ danych we wszystkie operacje, które chcesz, bez uciekania się do monad, klas i innych abstrakcyjnych rzeczy. Monady pozwalają jednak nie tylko pisać kod wielokrotnego użytku, ale także usuwać wszystkie zbędne szczegóły.
Jako przykład załóżmy, że chcemy filtrować listę. Najprostszym sposobem jest użycie
filter
funkcjifilter (> 3) [1..10]
:, która jest równa[4,5,6,7,8,9,10]
.Nieco bardziej skomplikowana wersja
filter
, która również przechodzi przez akumulator od lewej do prawej, toAby dostać wszystko
i
, tak, żei <= 10, sum [1..i] > 4, sum [1..i] < 25
możemy napisaćco jest równe
[3,4,5,6]
.Lub możemy przedefiniować
nub
funkcję, która usuwa zduplikowane elementy z listy, pod względemfilterAccum
:nub' [1,2,4,5,4,3,1,8,9,4]
równa[1,2,4,5,3,8,9]
. Lista jest przekazywana tutaj jako akumulator. Kod działa, ponieważ możliwe jest opuszczenie listy monad, więc całe obliczenia pozostają czyste (notElem
właściwie nie używają>>=
, ale mogą). Jednak nie jest możliwe bezpieczne opuszczenie monady IO (tzn. Nie można wykonać akcji IO i zwrócić czystej wartości - wartość zawsze będzie opakowana w monadę IO). Innym przykładem są zmienne tablice: po opuszczeniu monady ST, gdzie żyje zmienna tablica, nie można już aktualizować tablicy w stałym czasie. Potrzebujemy więc monadycznego filtrowania zControl.Monad
modułu:filterM
wykonuje akcję monadyczną dla wszystkich elementów z listy, uzyskując elementy, dla których powraca akcja monadycznaTrue
.Przykład filtrowania z tablicą:
drukuje
[1,2,4,5,3,8,9]
zgodnie z oczekiwaniami.I wersja z monadą IO, która pyta, które elementy zwrócić:
Na przykład
I jako ostateczną ilustrację
filterAccum
można zdefiniować w kategoriachfilterM
:z
StateT
monadą używaną pod maską, która jest zwykłym typem danych.Ten przykład pokazuje, że monady pozwalają nie tylko na abstrakcyjny kontekst obliczeniowy i pisanie czystego kodu wielokrotnego użytku (ze względu na możliwość komponowania monad, jak wyjaśnia @Carl), ale także na równomierne traktowanie typów danych i wbudowanych prymitywów.
źródło
Nie uważam, że
IO
powinna być postrzegana jako szczególnie wybitna monada, ale z pewnością jest to jedna z bardziej zdumiewających dla początkujących, więc wykorzystam ją dla wyjaśnienia.Naiwne budowanie systemu IO dla Haskell
Najprostszy możliwy do wyobrażenia system IO dla czysto funkcjonalnego języka (a właściwie tego, z którym Haskell zaczął) jest następujący:
Z lenistwem ta prosta sygnatura wystarcza do budowy interaktywnych programów terminalowych - choć bardzo ograniczona. Najbardziej frustrujące jest to, że możemy wyprowadzać tylko tekst. Co jeśli dodamy kilka bardziej ekscytujących możliwości wyjścia?
słodkie, ale oczywiście o wiele bardziej realistyczne „wyjście alternatywne” byłoby zapisywanie do pliku . Ale wtedy chcesz też jakiś sposób na czytanie z plików. Jakaś szansa?
Cóż, kiedy bierzemy nasz
main₁
program i po prostu potokujemy plik do procesu (używając urządzeń systemu operacyjnego), zasadniczo zaimplementowaliśmy odczyt plików. Gdybyśmy mogli uruchomić odczyt pliku z poziomu języka Haskell ...Użyłoby to „programu interaktywnego”
String->[Output]
, podało mu ciąg znaków uzyskany z pliku i wygenerowało nieinteraktywny program, który po prostu wykonuje dany program.Jest tutaj jeden problem: tak naprawdę nie mamy pojęcia, kiedy plik jest czytany. Ta
[Output]
lista z pewnością porządkuje wyjścia , ale nie otrzymujemy kolejności, kiedy dane zostaną wykonane.Rozwiązanie: uczyń zdarzenia wejściowe również pozycjami na liście rzeczy do zrobienia.
Ok, teraz możesz zauważyć brak równowagi: możesz odczytać plik i uzależnić wyjście od niego, ale nie możesz użyć zawartości pliku, aby zdecydować np. O odczytaniu innego pliku. Oczywiste rozwiązanie: spraw, aby wynik zdarzeń wejściowych był również czymś typu
IO
, nie tylkoOutput
. To z pewnością obejmuje proste wyjście tekstu, ale pozwala również na odczyt dodatkowych plików itp.Pozwoliłoby to teraz wyrazić dowolną operację na pliku, którą możesz chcieć w programie (choć może nie z dobrą wydajnością), ale jest to nieco skomplikowane:
main₃
daje całą listę działań. Dlaczego po prostu nie użyjemy podpisu:: IO₁
, który ma to jako specjalny przypadek?Listy nie dają już rzetelnego przeglądu przebiegu programu: większość kolejnych obliczeń zostanie „ogłoszona” tylko w wyniku niektórych operacji wprowadzania. Równie dobrze moglibyśmy porzucić strukturę listy i po prostu rozważyć „a potem zrobić” dla każdej operacji wyjściowej.
Nieźle!
Co to wszystko ma wspólnego z monadami?
W praktyce nie chcesz używać zwykłych konstruktorów do definiowania wszystkich swoich programów. Musiałoby istnieć kilka takich podstawowych konstruktorów, ale dla większości rzeczy na wyższym poziomie chcielibyśmy napisać funkcję z jakimś ładnym podpisem wysokiego poziomu. Okazuje się, że większość z nich wyglądałaby dość podobnie: akceptując jakąś sensownie wpisaną wartość, i w wyniku tego uzyskuje akcję IO.
Widocznie jest tutaj pewien wzorzec i lepiej go zapiszmy jako
Teraz zaczyna to wyglądać znajomo, ale nadal mamy do czynienia tylko z cienko ukrytymi prostymi funkcjami pod maską, a to ryzykowne: każda „akcja wartości” ma obowiązek przekazania wynikowej akcji dowolnej zawartej funkcji (w przeciwnym razie przepływ kontrolny całego programu jest łatwo zakłócany przez jedno źle zachowane działanie w środku). Lepiej wyraźmy to wymaganie. Okazuje się, że są to prawa monad , choć nie jestem pewien, czy naprawdę moglibyśmy je sformułować bez standardowych operatorów bind / join.
W każdym razie doszliśmy do sformułowania IO, które ma odpowiednią instancję monady:
Oczywiście nie jest to skuteczne wdrożenie IO, ale w zasadzie jest użyteczne.
źródło
IO3 a ≡ Cont IO2 a
. Ale miałem na myśli ten komentarz raczej jako ukłon w stronę tych, którzy już znają monadę kontynuacyjną, ponieważ nie ma ona reputacji przyjaznej dla początkujących.Monady są po prostu wygodnym narzędziem do rozwiązywania szeregu powtarzających się problemów. Po pierwsze, monady muszą być funktorami (tzn. Muszą obsługiwać mapowanie bez patrzenia na elementy (lub ich typ)), muszą także zapewniać operację wiązania (lub łączenia) oraz sposób tworzenia wartości monadycznej z typu elementu (
return
). Wreszciebind
ireturn
musi spełniać dwa równania (tożsamość lewa i prawa), zwane także prawami monady. (Alternatywnie można zdefiniować monady, aby miećflattening operation
zamiast wiązania).Lista monada jest powszechnie stosowany do czynienia z braku determinizmu. Operacja wiązania wybiera jeden element listy (intuicyjnie wszystkie w światach równoległych ), pozwala programiście wykonać z nimi pewne obliczenia, a następnie łączy wyniki ze wszystkich światów w jedną listę (łącząc lub spłaszczając listę zagnieżdżoną) ). Oto jak zdefiniować funkcję permutacji w monadycznym środowisku Haskell:
Oto przykładowa sesja repl :
Należy zauważyć, że monada listy nie jest w żaden sposób skutkiem ubocznym obliczeń. Struktura matematyczna będąca monadą (tj. Zgodna z wyżej wymienionymi interfejsami i prawami) nie implikuje skutków ubocznych, chociaż zjawiska wywołujące skutki uboczne często ładnie pasują do ramy monadycznej.
źródło
Monady służą zasadniczo do łączenia funkcji w łańcuch. Kropka.
Teraz sposób ich komponowania różni się w zależności od istniejących monad, co skutkuje różnymi zachowaniami (np. Do symulacji stanu zmiennego w monadzie stanowej).
Zamieszanie związane z monadami polega na tym, że będąc tak ogólnym, tj. Mechanizmem do komponowania funkcji, można ich używać do wielu rzeczy, w ten sposób prowadząc ludzi do przekonania, że monady dotyczą stanu, IO itp., Kiedy dotyczą tylko „funkcji komponowania” „.
Jedną interesującą rzeczą dotyczącą monad jest to, że wynikiem kompozycji jest zawsze typ „M a”, to znaczy wartość wewnątrz koperty oznaczonej „M”. Ta funkcja jest naprawdę miła w implementacji, na przykład wyraźne oddzielenie czystego od nieczystego kodu: zadeklaruj wszystkie nieczyste działania jako funkcje typu „IO a” i nie udostępniaj żadnej funkcji, definiując monadę IO, aby usunąć „ „wartość z wnętrza„ IO a ”. Powoduje to, że żadna funkcja nie może być czysta, a jednocześnie pobierać wartość z „IO a”, ponieważ nie ma sposobu na przyjęcie takiej wartości przy zachowaniu czystości (funkcja musi znajdować się w monadzie „IO”, aby użyć taka wartość). (UWAGA: cóż, nic nie jest idealne, więc „kaftan bezpieczeństwa IO” można zepsuć za pomocą „niebezpiecznePerformIO: IO a -> a”
źródło
Potrzebujesz monad, jeśli masz konstruktor typu i funkcje, które zwracają wartości z tej rodziny typów . W końcu chciałbyś połączyć te funkcje razem . Są to trzy kluczowe elementy, aby odpowiedzieć dlaczego .
Pozwól mi rozwinąć. Masz
Int
,String
aReal
i funkcje typuInt -> String
,String -> Real
i tak dalej. Możesz łatwo połączyć te funkcje, kończąc naInt -> Real
. Życie jest dobre.Pewnego dnia musisz stworzyć nową rodzinę typów . Może to być spowodowane tym, że należy wziąć pod uwagę możliwość zwrócenia żadnej wartości (
Maybe
), zwrócenia błędu (Either
), wielu wyników (List
) i tak dalej.Zauważ, że
Maybe
jest to konstruktor typów. Pobiera typ, jakInt
i zwraca nowy typMaybe Int
. Pierwszą rzeczą do zapamiętania, bez konstruktora typu, bez monady.Oczywiście chcesz użyć konstruktora typów w kodzie, a wkrótce skończysz z funkcjami takimi jak
Int -> Maybe String
iString -> Maybe Float
. Teraz nie możesz łatwo łączyć swoich funkcji. Życie nie jest już dobre.I tu na ratunek przychodzą monady. Pozwalają ci ponownie połączyć tego rodzaju funkcje. Musisz tylko zmienić skład . dla > == .
źródło