Różne sposoby oglądania monady

29

Podczas nauki języka Haskell spotkałem się z wieloma samouczkami próbującymi wyjaśnić, czym są monady i dlaczego monady są ważne w Haskell. Każda z nich używała analogii, więc łatwiej byłoby uchwycić sens. Ostatecznie mam 3 różne poglądy na to, czym jest monada:

Widok 1: Monada jako etykieta

Czasami myślę, że monada jako etykieta określonego typu. Na przykład funkcja typu:

myfunction :: IO Int

moja funkcja jest funkcją, która przy każdym wykonaniu daje wartość Int. Typ wyniku nie jest Int, ale IO Int. Tak więc IO jest etykietą wartości Int ostrzegającą użytkownika, aby wiedział, że wartość Int jest wynikiem procesu, w którym wykonano akcję IO.

W konsekwencji ta wartość Int została oznaczona jako wartość pochodząca z procesu z IO, dlatego ta wartość jest „brudna”. Twój proces nie jest już czysty.

Widok 2: Monada jako prywatna przestrzeń, w której mogą się zdarzyć nieprzyjemne rzeczy.

W systemie, w którym cały proces jest czysty i surowy, czasami trzeba mieć skutki uboczne. Tak więc monada to tylko niewielka przestrzeń, która pozwala ci na robienie nieprzyjemnych efektów ubocznych. W tej przestrzeni możesz uciec z czystego świata, przejść nieczyste, dokonać procesu, a następnie powrócić z wartością.

Widok 3: Monada jak w teorii kategorii

Tego poglądu nie do końca rozumiem. Monada jest po prostu funktorem tej samej kategorii lub podkategorii. Na przykład masz wartości Int i jako podkategoria IO Int, które są wartościami Int wygenerowanymi po procesie IO.

Czy te widoki są prawidłowe? Który jest bardziej dokładny?

Oni
źródło
5
# 2 nie jest ogólnie tym, czym jest monada. W rzeczywistości jest on ograniczony do IO i nie jest użytecznym widokiem (por. Czym nie jest monada ). Również „ścisłe” jest ogólnie używane w celu nazwania własności, której Haskell nie posiada (a mianowicie ścisłej oceny). Nawiasem mówiąc, Monady też tego nie zmieniają (ponownie zobacz, czym nie jest Monada).
3
Technicznie tylko trzeci jest poprawny. Monada jest endofunkcją, dla której zdefiniowano operacje specjalne - promocję i wiązanie. Monady są liczne - monada listowa to doskonały przykład na intuicję za monadami. Urządzenia readS są jeszcze lepsze. Zaskakujące jest to, że monady są użyteczne jako narzędzia do pośredniczenia w wątkach w czystym języku funkcjonalnym. Nie jest to właściwość definiująca monady: to przypadek, że wątki stanu mogą być realizowane na ich warunkach. To samo dotyczy IO.
permeakra
Common Lisp ma własny kompilator jako część języka. Haskell ma Monady.
Czy Ness

Odpowiedzi:

33

Widoki 1 i 2 są ogólnie niepoprawne.

  1. Każdy rodzaj danych * -> *może działać jako etykieta, monady to znacznie więcej.
  2. (Z wyjątkiem IOmonady) obliczenia w monadzie nie są nieczyste. Po prostu reprezentują obliczenia, które postrzegamy jako mające skutki uboczne, ale są czyste.

Oba te nieporozumienia wynikają z koncentracji na IOmonadzie, która w rzeczywistości jest trochę wyjątkowa.

Spróbuję trochę rozwinąć # 3, nie wchodząc w teorię kategorii, jeśli to możliwe.


Standardowe obliczenia

Wszystkie obliczenia w funkcjonalnego języka programowania może być postrzegana jako funkcje z typem źródłowego i docelowego typu: f :: a -> b. Jeśli funkcja ma więcej niż jeden argument, możemy przekonwertować ją na funkcję jednego argumentu przez curry (patrz także wiki Haskell ). A jeśli mamy tylko wartości x :: a(0 funkcji z argumentami), możemy przekształcić go w funkcję, która pobiera argument typu urządzenia : (\_ -> x) :: () -> a.

Możemy budować bardziej złożone programy z prostszych, tworząc takie funkcje za pomocą .operatora. Na przykład, jeśli mamy f :: a -> bi g :: b -> cdostaniemy g . f :: a -> c. Zauważ, że działa to również w przypadku naszych przeliczonych wartości: jeśli mamy x :: ai przekonwertujemy to na naszą reprezentację, otrzymamy f . ((\_ -> x) :: () -> a) :: () -> b.

Ta reprezentacja ma kilka bardzo ważnych właściwości, a mianowicie:

  • Mamy bardzo specjalny Funkcja - tożsamość funkcję id :: a -> adla każdego typu a. Jest to element tożsamości w odniesieniu do .: fjest równy f . idi do id . f.
  • Operator kompozycji funkcji .jest asocjacyjny .

Obliczenia monadyczne

Załóżmy, że chcemy wybrać i pracować z jakąś specjalną kategorią obliczeń, której wynik zawiera coś więcej niż tylko jedną zwracaną wartość. Nie chcemy sprecyzować, co oznacza „coś więcej”, chcemy zachować jak najbardziej ogólną sytuację. Najbardziej ogólnym sposobem przedstawienia „czegoś więcej” jest przedstawienie go jako funkcji typu - rodzaju mrodzaju * -> *(tzn. Konwertuje jeden typ na inny). Tak więc dla każdej kategorii obliczeń, z którymi chcemy pracować, będziemy mieli jakąś funkcję typu m :: * -> *. (W Haskell, mjest [], IO, Maybe, itd.) I kategoria wola zawiera wszystkie funkcje typów a -> m b.

Teraz chcielibyśmy pracować z funkcjami w takiej kategorii w taki sam sposób, jak w przypadku podstawowym. Chcemy móc komponować te funkcje, chcemy, aby kompozycja była asocjacyjna i chcemy mieć tożsamość. Potrzebujemy:

  • Aby mieć operatora (nazwijmy go <=<), który komponuje funkcje f :: a -> m bi tworzy g :: b -> m ccoś takiego g <=< f :: a -> m c. I musi być asocjacyjny.
  • Aby mieć jakąś funkcję tożsamości dla każdego typu, nazwijmy ją return. Chcemy również, aby to f <=< returnbyło to samo fi co return <=< f.

Każdy, m :: * -> *dla którego mamy takie funkcje returni <=<nazywa się monadą . Pozwala nam tworzyć złożone obliczenia z prostszych, tak jak w przypadku podstawowym, ale teraz typy wartości zwracanych są przekształcane przez m.

(Właściwie nieco nadużyłem tutaj terminu kategoria . W sensie teorii kategorii możemy nazwać naszą konstrukcję kategorią tylko wtedy, gdy wiemy, że przestrzega ona tych praw.)

Monady w Haskell

W Haskell (i innych językach funkcjonalnych) przeważnie pracujemy z wartościami, a nie z funkcjami typów () -> a. Zamiast definiować <=<dla każdej monady, definiujemy funkcję (>>=) :: m a -> (a -> m b) -> m b. Taka alternatywna definicja jest równoważna, możemy wyrazić >>=za pomocą <=<i odwrotnie (spróbuj jako ćwiczenie lub zobacz źródła ). Zasada jest teraz mniej oczywista, ale pozostaje ta sama: nasze wyniki są zawsze typami, m aa my tworzymy funkcje typów a -> m b.

W przypadku każdej monady, którą tworzymy, nie możemy zapominać o sprawdzeniu tego returni <=<posiadaniu wymaganych właściwości: asocjatywności i tożsamości lewej / prawej. Wyrażone za pomocą returni >>=nazywane są prawami monady .

Przykład - listy

Jeśli zdecydujemy msię być [], otrzymamy kategorię funkcji typów a -> [b]. Takie funkcje reprezentują obliczenia niedeterministyczne, których wynikiem może być jedna lub więcej wartości, ale także żadnych wartości. Daje to początek tak zwanej monadzie listy . Skład f :: a -> [b]i g :: b -> [c]działa w następujący sposób: g <=< f :: a -> [c]oznacza obliczenie wszystkich możliwych wyników typu [b], zastosowanie gdo każdego z nich i zebranie wszystkich wyników na jednej liście. Wyrażony w Haskell

return :: a -> [a]
return x = [x]
(<=<) :: (b -> [c]) -> (a -> [b]) -> (a -> [c])
g (<=<) f  = concat . map g . f

lub używając >>=

(>>=) :: [a] -> (a -> [b]) -> [b]
x >>= f  = concat (map f x)

Zauważ, że w tym przykładzie typy zwracane były, [a]więc możliwe, że nie zawierały żadnej wartości typu a. Rzeczywiście nie ma takiego wymogu dla monady, aby typ zwracany miał takie wartości. Niektóre monady zawsze mają (jak IOlub State), ale niektóre nie, jak []lub Maybe.

Monada IO

Jak wspomniałem, IOmonada jest nieco wyjątkowa. Wartość typu IO aoznacza wartość typu azbudowaną przez interakcję ze środowiskiem programu. Tak więc (w przeciwieństwie do wszystkich innych monad) nie możemy opisać wartości typu IO aza pomocą czystej konstrukcji. Oto IOpo prostu tag lub etykieta, która odróżnia obliczenia oddziałujące ze środowiskiem. Jest to (jedyny przypadek), w którym widoki nr 1 i nr 2 są poprawne.

W przypadku IOmonady:

  • Skład f :: a -> IO bi g :: b -> IO cśrodki: Oblicz, fktóry wchodzi w interakcje ze środowiskiem, a następnie oblicz, gktóry używa wartości i oblicza wynik interakcji z otoczeniem.
  • returnpo prostu dodaje do wartości IO„tag” (po prostu „obliczamy” wynik, utrzymując nienaruszone środowisko).
  • Prawa monady (asocjatywność, tożsamość) są gwarantowane przez kompilator.

Niektóre uwagi:

  1. Ponieważ obliczenia monadyczne zawsze mają typ wyniku m a, nie ma sposobu na „ucieczkę” od IOmonady. Oznacza to, że: gdy obliczenia wchodzą w interakcje ze środowiskiem, nie można zbudować obliczeń, które by nie działały.
  2. Kiedy programista funkcjonalna nie wie, jak zrobić coś w sposób czysty, (S) może on (jako ostatni ośrodek) Zaprogramuj zadanie jakiejś stanowej obliczeń w IOmonady. Dlatego IOczęsto nazywany jest bin sinem programisty .
  3. Zauważ, że w nieczystym świecie (w sensie programowania funkcjonalnego) odczyt wartości może również zmienić środowisko (np. Zużywać dane użytkownika). Dlatego takie funkcje getCharmuszą mieć typ wyniku IO something.
Petr Pudlák
źródło
3
Świetna odpowiedź. Wyjaśnię, że IOnie ma specjalnej semantyki z punktu widzenia języka. To nie specjalnego, to zachowuje się jak każdy inny kod. Tylko implementacja biblioteki wykonawczej jest wyjątkowa. Istnieje również specjalny sposób na ucieczkę ( unsafePerformIO). Myślę, że jest to ważne, ponieważ ludzie często myślą o IOspecjalnym elemencie językowym lub deklaratywnym znaczniku. Nie jest.
usr
2
@usr Dobra uwaga. Dodam, że niebezpieczne SafePerformIO jest naprawdę niebezpieczne i powinno być używane tylko przez ekspertów. Pozwala ci wszystko zepsuć, na przykład możesz stworzyć funkcję, coerce :: a -> bktóra konwertuje dowolne dwa typy (aw większości przypadków powoduje awarię programu). Zobacz ten przykład - możesz przekonwertować nawet funkcję na Intitp.
Petr Pudlák,
Inną „specjalną magiczną” monadą byłaby ST, która pozwala zadeklarować odniesienia do pamięci, z której można czytać i zapisywać według własnego uznania (chociaż tylko w obrębie monady), a następnie można wyodrębnić wynik, dzwoniącrunST :: (forall s. GHC.ST.ST s a) -> a
sara
5

Widok 1: Monada jako etykieta

„W konsekwencji ta wartość Int została oznaczona jako wartość pochodząca z procesu z IO, dlatego ta wartość jest„ brudna ”.”

„IO Int” zasadniczo nie jest wartością Int (chociaż może być w niektórych przypadkach, np. „Return 3”). Jest to procedura, która generuje pewną wartość Int. Różne wykonania tej „procedury” mogą dawać różne wartości Int.

Monada m jest osadzonym (imperatywnym) „językiem programowania”: w tym języku można zdefiniować niektóre „procedury”. Wartość monadyczna (typu ma) jest procedurą w tym „języku programowania”, która generuje wartość typu a.

Na przykład:

foo :: IO Int

to jakaś procedura, która generuje wartość typu Int.

Następnie:

bar :: IO (Int, Int)
bar = do
  a <- foo
  b <- foo
  return (a,b)

jest jakaś procedura, która daje dwa (być może różne) Ints.

Każdy taki „język” obsługuje niektóre operacje:

  • dwie procedury (ma i mb) mogą być „połączone”: możesz stworzyć większą procedurę (ma >> mb) wykonaną z pierwszej, a następnie drugiej;

  • co więcej, wynik (a) pierwszego może wpływać na drugi (ma >> = \ a -> ...);

  • procedura (return x) może dać pewną stałą wartość (x).

Różne wbudowane języki programowania różnią się od obsługiwanych przez nich rzeczy, takich jak:

  • dające losowe wartości;
  • „rozwidlenie” (monada []);
  • wyjątki (rzut / złap) (The Either e monad);
  • wyraźna kontynuacja / obsługa callcc;
  • wysyłanie / odbieranie wiadomości do innych „agentów”;
  • tworzyć, ustawiać i odczytywać zmienne (lokalne dla tego języka programowania) (monada ST).
ysdx
źródło
1

Nie myl typu monadycznego z klasą monad.

Typ monadyczny (tj. Typ będący instancją klasy monad) rozwiązałby konkretny problem (w zasadzie każdy typ monadyczny rozwiązuje inny): State, Random, Może, IO. Wszystkie są typami z kontekstem (to, co nazywacie „etykietą”, ale nie to czyni ich monadą).

Dla wszystkich potrzebna jest „operacja łączenia z wyborem” (jedna operacja zależy od wyniku poprzedniej). W grę wchodzi klasa monad: niech twój typ (rozwiązanie danego problemu) będzie instancją klasy monad, a problem łańcuchowy zostanie rozwiązany.

Zobacz, co rozwiązuje klasa monad?

cibercitizen1
źródło