Funktory i Monady

Teoria kategorii jest dość abstrakcyjnym działem matematyki mówiącym o przekształceniach (morfizmach) między obiektami (kategoriami). Wywodziła się początkowo z obszaru topologii i przekształceń topologicznych, jej ogólność pozwoliła jednak skutecznie opisać wszelkie rodzaje przekształceń, pośród których interesujące miejce zajmują funkcje w sensie znanym z teorii zbiorów, czy też analizy matematycznej. Poniższa strona tłumaczy w przystępny sposób, jak algebra liniowa może być opisana językiem teorii kategorii. Haskell jest silnie zakorzeniony w teorii kategorii (przekształceniem jest tutaj po prostu funkcja), co silnie rzutuje na dwie jego cechy:

• uniwersalne wzorce projektowe działające na wszelkich przekształceniach, tj. możliwe jest stworzenie takich typeclass, które mogą być zaaplikowane na dowolnych funkcjach. To jest plus, nie każdy język to potrafi.
• dziwne nazewnictwo: funktory, monoidy, monady, soczewki, itd., itp. Często właśnie to nazewnictwo i nadmierna formalność odstrasza początkujących programistów haskella. To jest minus.

Dzisiaj wprowadzimy dwa terminy (dwie typeclass'y) pochodzące z teorii kategorii: funktory i monady.

Zaczniemy od rzeczy prostej - funktor wiąże się z bardzo prostym przekształceniem fmap (które zachowuje się dokładnie tak samo jak znane nam map). Powiemy, że F jest funktorem, jeśli są spełnione dwa prawa funktorów:

1. fmap id F = F (równoważnie fmap id = id), gdzie id to przekształcenie identycznościowe: id F = F. Oznacza to tyle, że każdy funktor przeształcony przez fmap id nie ulega zmianie.
2. fmap (f . g) F = fmap f (fmap g F) - czyli fmap stosowane na funktorze jest rozdzielne względem operatora złożenia funkcji, zachowując kolejność ich wykonania.

Żeby umożliwić powszechne stosowanie fmap (a co za tym idzie map), Haskell dostarcza klasę Functor:

Ćwiczenie: sprawdź, czy typy List i Maybe są funktorami.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Jedyne, co musimy zrobić, to zaimplementować jedną prostą funkcję! Warto zauważyć, że system typów Haskella nie jest w stanie sprawdzić, czy fmap jest zaimplementowany zgodnie z prawami funktorów. Ciężar sprawdzenia tych praw ciąży na programiście.

Prostym przykładem instacji tej klasy byłby typ Maybe:

instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing

lub lista:

instance Functor List where  
    fmap = map

map spełnia prawa fmap!

Z punktu widzenie programisty funktory pozwalają wykonywać operację w pewnym kontekście obliczeniowym. Takim kontekst może być na przykład przynależność do kolekcji danych, funktory pozwala na wykonanie operacji „wewnątrz” kolekcji. Innym kontekstem będzie na przykład kontekst wejścia / wyjścia jak w przypadku IO. IO obiecuje nam jakiegoś stringa, którego jeszcze nie ma, użytkownik może go wpisać - może nie wpisać - ta niepewność co do formy danych wejściowych to właśnie kontekst obliczeniowy - fmap może zajrzeć do środka IO i przekształcić dane wejściowe. Podobnym przykładem są Maybe i Either, gdzie niepewność wynika z możliwości brakujących danych / błędów.

Monady, podobnie do funktorów, zachowują się szczególnie względem zadanych przekształceń - tutaj jednak klasa wygląda na trochę bardziej skomplikowaną:

    class Monad m where  
        return :: a -> m a  
 
        (>>=) :: m a -> (a -> m b) -> m b  
 
        (>>) :: m a -> m b -> m b  
        x >> y = x >>= \_ -> y  
 
        fail :: String -> m a  
        fail msg = error msg  

Nie należy jednak panikować :) Zacznijmy od góry:

• return: wkłada wartość w kontekst, np. return 3::(Maybe Int) = Just 3 lub return 3::([Int]) = [3]. Po prostu opakowujemy wartość, chociaż sama nazwa return jest myląca…
• >>= to tzw. operator wiążący (bind operator), który działa podobnie do fmap. Różnica tkwi w tym, że przekazywana funkcja zwraca od razu opakowaną wartość (w fmap funkcja nie wiedziała nic o opakowaniu w kontekst). Pozwala on na łańcuchowanie przekształceń na monadach, za chwilę pokażemy jak to działa…
• >> to wersja »=, która po prostu zastępują aktualną wartość w pudełku nową - jest już domyślne zaimplementowana
• fail odpowiada za obsługę błędów (jakich - pokażemy za chwilę…). Domyślna implementacja wywala wyjątek, więc nie jest zalecana :)

Tak naprawdę kluczowe są dwa przekształcenia return i >>=, i z nimi się wiążą poniższe prawa monad:

1. return x >>= f to tyle, co f x. Pamiętajmy, że funkcja f ma typ (a → m b), czyli zwraca już wartość w kontekście danej monady. Jeżeli zatem wywołamy f x to wynik będzie już w konkteście danej monady. Operator >>= pozwala na uzyskanie tego samego efektu z wartościami już opakowanymi.
2. m >>= return to tyle samo, co samo m. Innymi słowy, jeżeli wartość jest już w konteście (a skoro używamy >>=, to musi już być), to kolejne włożenie jej w ten sam kontekst nic nie zmienia
3. (m >>= f) >>= g oznacza to samo, co m >>= (\x -> f x >>= g), czyli kolejność użycia operatora >>= nie ma znaczenia, jest on łączny.

Tyle z teorii, poniżej dwa proste przykłady znane już jako funktory…

instance Monad Maybe where  
    return x = Just x  
    Nothing >>= f = Nothing  
    Just x >>= f  = f x  
    fail _ = Nothing 

Ćwiczenia:

1. Sprawdź, co zwraca return 5::(Maybe Int)?
2. Sprawdź, co zwraca Just 3 >>= (\x -> return (x + 1)) >>= (\x -> return (x * 2))
3. Sprawdź, co zwraca Just 3 >> Just 5

instance Monad [] where  
    return x = [x]  
    xs >>= f = concat (map f xs)  
    fail _ = []  

Ćwiczenia:

1. Sprawdź, co zwraca return 5::[Int]
2. Sprawdź, co zwracają [1] >>= (\x -> [x,-x]) i [1] >>= (\x -> [x,-x]) >>= (\x -> [x,-x])
3. Sprawdź, co zwraca [1] >> [1,2,3]

Operatory >>= i >> mają na celu tworzenia łańcuchów przekształceń danej monady, ale ich użycie jest dość niewygodne - szczególnie w przypadkach długich łańcuchów, w których są błędy. Dlatego powstała notacja do, której używaliśmy na poprzednich zajęciach — IO to też monada! Zacznijmy od w miarę złożonego łąńucha >>=:

[1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)

Wynik może być zaskakujący! Kto spodziewał się [(1,'a'),(1,'b'),(2,'a'),(2,'b')]? Wynika to z tego, że n przyjmuje wartości z [1,2], a ch wartości z ['a','b'], teraz na sam koniec jest zwracana para '(n,ch)' opakowana w listę przez return. Zrozumienie tego na podstawie pierwszego wyrażenia wydaje się trudne, dlatego w haskellu powstały dwa rodzaje syntax sugar:

• list comprehensions, które już znamy :) Tak - one po prostu używają list jako monad!
• notacja 'do', w której powyższe wyrażenie przedstawia się następująco:

listOfTuples :: [(Int,Char)]  
listOfTuples = do  
    n <- [1,2]  
    ch <- ['a','b']  
    return (n,ch)  

Prawda, że podobne? Pozbywamy się >>='' i odwracamy kierunek strzałek, żeby było dokładnie widać skąd pochodzi która zmienna :) Jeżeli chcemy zasymulować operator ''», możemy po prostu wrzucić monadę bez strzałeczki:

anotherChain = do
    n <- [1,2]
    ch <- ['a', 'b']
    [3, 4]

Ćwiczenie: Jaki jest wynik powyższego łańcucha?

Na koniec wyjaśnimy, po co jest funkcja fail w klasie Monad. Przyczyna jest prosta, w notacji do po lewej stronie strzałki można robić pattern matching. Jest to bardzo pożyteczna zaleta notacji do. Ale co, kiedy pattern matching zawiedzie?

Ćwiczenie: spróbuj zrobić nieudany pattern matching w notacji do. Jaki będzie efekt?

Możliwość łańcuchowania operacji na monadach jest nie do przecenienia i aktualnie jest implementowana we wszystkich nowoczesnych językach programowania. Nie oznacza to, że dany język musi mieć wsparcie dla definiowania Monad tak jak Haskell. Poszczególne monady można implementować w Pythonie, Javie, etc. Po prostu nie ma tam takiego ogólnego mechanizmu jak typeclass do ujęcia wszystkich monad naraz.

Sławny i popularny przykład zastosowania monad to railway programming, czyli funkcyjny sposób obsługi błędów.

Dzisiejsze zadania będą dotyczyć drzewa binarnego opisanego w następujący sposób:

data Tree a = Empty | Leaf a | Node (Tree a) (Tree a)

1. Zaimplementuj klasę Functor dla nowego typu Tree.
2. Zaimplementuj klasę Monad dla tego samego typu.
3. Przeczytaj o monadzie State. Zaimplementuj poniższe operacje jako stateful computations dla starego drzewa z poprzedniego laboratorium:
   • insert - umieszcza element w drzewie
   • removeAll - usuwa wszystkie elementy spełniające zadany warunek z drzewa i zwraca je w liście jako wynik
   • search - sprawdza, czy element jest w drzewie
4. Zadanie ekstra - zaimplementuj te same operacje dla nowego drzewa
   • podpowiedź: tree.png

instance Applicative Tree where
   pure x = Leaf x
   _ <*> Empty = Empty
   (Leaf f) <*> (Leaf x) = Leaf (f x)
   (Leaf f) <*> (Node x y) = Node (fmap f x) (fmap f y)