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.

1. Zaimplementuj klasę Functor dla typu Tree zdefiniowanego na poprzednich zajęciach
2. Zaimplementuj klasę Monad dla tego samego typu ''Tree''
3. Przeczytaj o monadzie State. Zaimplementuj wszystkie operacje na drzewie z poprzednich zajęć jako stateful computations.

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