[[
✎ pl:dydaktyka:pp:haskell:lab-monads
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Funktory i Monady ====== [[https://pl.wikipedia.org/wiki/Teoria_kategorii|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. [[https://graphicallinearalgebra.net/|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. ===== Funktory ===== 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//: - ''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. - ''fmap (f . g) F = fmap f (fmap g F)'' - czyli ''fmap'' stosowane na funktorze jest [[https://pl.wikipedia.org/wiki/Rozdzielno%C5%9B%C4%87_dzia%C5%82ania|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. ----- <code haskell> class Functor f where fmap :: (a -> b) -> f a -> f b </code> 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'': <code haskell> instance Functor Maybe where fmap f (Just x) = Just (f x) fmap f Nothing = Nothing </code> lub lista: <code haskell> instance Functor List where fmap = map </code> ''map'' spełnia prawa ''fmap''! ==== Na co to komu? A komu to potrzebne? ==== 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 ===== Monady, podobnie do funktorów, zachowują się szczególnie względem zadanych przekształceń - tutaj jednak klasa wygląda na trochę bardziej skomplikowaną: <code haskell> 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 </code> 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: - ''%%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. - ''%%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 - ''%%(m >>= f) >>= g%%'' oznacza to samo, co ''%%m >>= (\x -> f x >>= g)%%'', czyli kolejność użycia operatora ''%%>>=%%'' nie ma znaczenia, jest on [[https://pl.wikipedia.org/wiki/%C5%81%C4%85czno%C5%9B%C4%87_(matematyka)|łączny]]. ==== Przykłady ==== Tyle z teorii, poniżej dwa proste przykłady znane już jako funktory... <code haskell> instance Monad Maybe where return x = Just x Nothing >>= f = Nothing Just x >>= f = f x fail _ = Nothing </code> ----- **Ćwiczenia:** - Sprawdź, co zwraca ''return 5::(Maybe Int)''? - Sprawdź, co zwraca ''%%Just 3 >>= (\x -> return (x + 1)) >>= (\x -> return (x * 2))%%'' - Sprawdź, co zwraca ''%%Just 3 >> Just 5%%'' ----- <code haskell> instance Monad [] where return x = [x] xs >>= f = concat (map f xs) fail _ = [] </code> ----- **Ćwiczenia:** - Sprawdź, co zwraca ''return 5::[Int]'' - Sprawdź, co zwracają ''%%[1] >>= (\x -> [x,-x])%%'' i ''%%[1] >>= (\x -> [x,-x]) >>= (\x -> [x,-x])%%'' - Sprawdź, co zwraca ''%%[1] >> [1,2,3]%%'' ----- ==== Notacja 'Do' ==== 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 ''%%>>=%%'': <code haskell> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch) </code> 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: <code haskell> listOfTuples :: [(Int,Char)] listOfTuples = do n <- [1,2] ch <- ['a','b'] return (n,ch) </code> 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: <code haskell> anotherChain = do n <- [1,2] ch <- ['a', 'b'] [3, 4] </code> **Ćwiczenie:** Jaki jest wynik powyższego łańcucha? === Fail === 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? ==== A po co to? ==== 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 [[https://fsharpforfunandprofit.com/rop/|railway programming]], czyli funkcyjny sposób obsługi błędów. ===== Zadania: ===== Dzisiejsze zadania będą dotyczyć drzewa binarnego opisanego w następujący sposób: <code haskell> data Tree a = Empty | Leaf a | Node (Tree a) (Tree a) </code> - Zaimplementuj klasę ''Functor'' dla nowego typu ''Tree''. - Zaimplementuj klasę ''Monad'' dla tego samego typu. - Przeczytaj o monadzie [[http://learnyouahaskell.com/for-a-few-monads-more#state|State]]. Zaimplementuj poniższe operacje jako //stateful computations// dla **starego** drzewa z [[https://ai.ia.agh.edu.pl/pl:dydaktyka:pp:haskell:lab-types|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 - Zadanie ekstra - zaimplementuj te same operacje dla nowego drzewa * podpowiedź: {{tree.png?linkonly=yes}} <WRAP center round important 60%> **UWAGA**: w zależności od wersji Haskella, może być konieczne również zaimplementowanie klasy ''Applicative'' (jako wymagania do bycia monadą). Klasa ''Applicative'' umożliwa używanie funkcji opakowanych monadą. Poniżej jest przykładowa implementacja ''Applicative'', która jest poprawna, ale akceptuje tylko pojedyncze funkcje opakowane w liściach - na dzisiaj wystarczy: * ''pure'' to dokładnie to samo, co ''return''. Tak naprawdę w Monadzie zawsze można pisać: ''return = pure'' * ''%%<*>%%'' aplikuje funkcję opakowaną monadą, taki ''fmap'', który wyjmuje funkcję z pudełka, a nie ma go pod ręką <code haskell> 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) </code> </WRAP>
pl/dydaktyka/pp/haskell/lab-monads.txt
· ostatnio zmienione: 2020/06/01 15:34 przez
msl
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry