Dlaczego potrzebujemy monad?

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?

Dlaczego potrzebujemy monad?

1. Chcemy programować tylko za pomocą funkcji . (w końcu „programowanie funkcjonalne (FP)”).

2. 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ępnie f, po prostu napisz f(g(x,y)). W ten sposób, „program” jest funkcją, a także: main = f(g(x,y)). Dobrze, ale ...

3. 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ólmy g : Real,Real -> Real | Nothing(funkcja z dwóch rzeczywistych w rzeczywistą lub rzeczywistą).

4. 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 ...

5. Co się teraz stanie f(g(x,y))? fnie jest gotowy do spożycia Maybe Real. I nie chcemy zmieniać każdej funkcji, z którą możemy się połączyć, gaby 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ć gsię f). Chcemy >>=uzyskać gdane wyjściowe, sprawdzić je, a jeśli Nothingtak, to nie dzwoń fi nie wracaj Nothing; lub wręcz przeciwnie, wyodrębnij pudełko Reali karm fje nim. (Ten algorytm jest właśnie realizacja >>=dla Maybetypu). Należy również pamiętać, że >>=należy napisać tylko raz dla „typu boksu” (inne pole, inny algorytm dostosowujący).

6. 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 gzwracają te „wartości w pudełkach”. 2. Poproś kompozytora / linkera, g >>= faby pomógł gpodłączyć wyjście do fwejścia, więc nie musimy go fw ogóle zmieniać .

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

Całkowite szczęście!

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 IOtyp sam sobie z tym radzi. Istniejący monadycznego desugaring z dobloków można zastąpić desugaring do bindIO, returnIOi failIO, 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)i bar :: (a -> Maybe b)? foo . barnie sprawdza typu, ponieważ bi Maybe bnie są tego samego typu.

Ale ... to prawie racja. Chcesz trochę swobody. Chcesz być w stanie traktować to Maybe btak, jakby to było w zasadzie b. 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 (.)i idforma konstruktu matematycznego znanego jako kategoria . Istnieją jednak inne sposoby tworzenia kategorii. Na przykład kategoria Kleisli pozwala nieco rozszerzyć komponowane obiekty. Kategoria Kleisli dla Maybeskładałaby się z (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)i id :: a -> Maybe a. Oznacza to, że obiekty w kategorii rozszerzają się (->)o Maybe, 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ż tylko Maybe. Działają z każdym typem, który może złożyć odpowiednią kategorię, przestrzegając praw kategorii.

1. Lewa tożsamość: id . f =f
2. Właściwa tożsamość: f . id =f
3. Stowarzyszenie: 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„s returnjest taki sam jak Kleisli id. 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 Monadabstrakcja 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.

Benjamin Pierce powiedział w TAPL

System typów można traktować jako obliczanie pewnego rodzaju statycznego przybliżenia zachowań terminów w programie w czasie wykonywania.

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 filterfunkcji filter (> 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, to

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

Aby dostać wszystko i, tak, że i <= 10, sum [1..i] > 4, sum [1..i] < 25możemy napisać

filterAccum (\a x -> let a' = a + x in (a' > 4 && a' < 25, a')) 0 [1..10]

co jest równe [3,4,5,6].

Lub możemy przedefiniować nubfunkcję, która usuwa zduplikowane elementy z listy, pod względem filterAccum:

nub' = filterAccum (\a x -> (x `notElem` a, x:a)) []

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 ( notElemwł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 z Control.Monadmodułu:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
   flg <- p x
   ys  <- filterM p xs
   return (if flg then x:ys else ys)

filterMwykonuje akcję monadyczną dla wszystkich elementów z listy, uzyskując elementy, dla których powraca akcja monadyczna True.

Przykład filtrowania z tablicą:

nub' xs = runST $ do
        arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool)
        let p i = readArray arr i <* writeArray arr i False
        filterM p xs

main = print $ nub' [1,2,4,5,4,3,1,8,9,4]

drukuje [1,2,4,5,3,8,9]zgodnie z oczekiwaniami.

I wersja z monadą IO, która pyta, które elementy zwrócić:

main = filterM p [1,2,4,5] >>= print where
    p i = putStrLn ("return " ++ show i ++ "?") *> readLn

Na przykład

return 1? -- output
True      -- input
return 2?
False
return 4?
False
return 5?
True
[1,5]     -- output

I jako ostateczną ilustrację filterAccummożna zdefiniować w kategoriach filterM:

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

z StateTmonadą 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.

Nie uważam, że IOpowinna 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:

main₀ :: String -> String
main₀ _ = "Hello World"

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?

data Output = TxtOutput String
            | Beep Frequency

main₁ :: String -> [Output]
main₁ _ = [ TxtOutput "Hello World"
          -- , Beep 440  -- for debugging
          ]

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

readFile :: Filepath -> (String -> [Output]) -> [Output]

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.

data IO₀ = TxtOut String
         | TxtIn (String -> [Output])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [Output])
         | Beep Double

main₂ :: String -> [IO₀]
main₂ _ = [ FileRead "/dev/null" $ \_ ->
             [TxtOutput "Hello World"]
          ]

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 tylko Output. To z pewnością obejmuje proste wyjście tekstu, ale pozwala również na odczyt dodatkowych plików itp.

data IO₁ = TxtOut String
         | TxtIn (String -> [IO₁])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [IO₁])
         | Beep Double

main₃ :: String -> [IO₁]
main₃ _ = [ TxtIn $ \_ ->
             [TxtOut "Hello World"]
          ]

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.

data IO₂ = TxtOut String IO₂
         | TxtIn (String -> IO₂)
         | Terminate

main₄ :: IO₂
main₄ = TxtIn $ \_ ->
         TxtOut "Hello World"
          Terminate

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.

getTime :: (UTCTime -> IO₂) -> IO₂
randomRIO :: Random r => (r,r) -> (r -> IO₂) -> IO₂
findFile :: RegEx -> (Maybe FilePath -> IO₂) -> IO₂

Widocznie jest tutaj pewien wzorzec i lepiej go zapiszmy jako

type IO₃ a = (a -> IO₂) -> IO₂    -- If this reminds you of continuation-passing
                                  -- style, you're right.

getTime :: IO₃ UTCTime
randomRIO :: Random r => (r,r) -> IO₃ r
findFile :: RegEx -> IO₃ (Maybe FilePath)

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:

data IO₄ a = TxtOut String (IO₄ a)
           | TxtIn (String -> IO₄ a)
           | TerminateWith a

txtOut :: String -> IO₄ ()
txtOut s = TxtOut s $ TerminateWith ()

txtIn :: IO₄ String
txtIn = TxtIn $ TerminateWith

instance Functor IO₄ where
  fmap f (TerminateWith a) = TerminateWith $ f a
  fmap f (TxtIn g) = TxtIn $ fmap f . g
  fmap f (TxtOut s c) = TxtOut s $ fmap f c

instance Applicative IO₄ where
  pure = TerminateWith
  (<*>) = ap

instance Monad IO₄ where
  TerminateWith x >>= f = f x
  TxtOut s c >>= f = TxtOut s $ c >>= f
  TxtIn g >>= f = TxtIn $ (>>=f) . g

Oczywiście nie jest to skuteczne wdrożenie IO, ale w zasadzie jest użyteczne.

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). Wreszcie bindi returnmusi 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:

perm [e] = [[e]]
perm l = do (leader, index) <- zip l [0 :: Int ..]
            let shortened = take index l ++ drop (index + 1) l
            trailer <- perm shortened
            return (leader : trailer)

Oto przykładowa sesja repl :

*Main> perm "a"
["a"]
*Main> perm "ab"
["ab","ba"]
*Main> perm ""
[]
*Main> perm "abc"
["abc","acb","bac","bca","cab","cba"]

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.

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”

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, Stringa Reali funkcje typu Int -> String, String -> Reali 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 Maybejest to konstruktor typów. Pobiera typ, jak Inti zwraca nowy typ Maybe 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 StringiString -> 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 > == .