26.02.2019: Wprowadzenie

Wprowadzenie do Haskella

1. Haskell Brooks Curry
2. Pojęcie czystej funkcji

   Funkcja która nie jest czysta

       int x = 2;
       ...
       int myAdd (int y) {
         return x + y;
       }
       ...
       print myAdd (3);
     

   Czysta funkcja

     int myAdd (int y) {
       return 2 + y;
     }
     ...
     print myAdd (3)
     

3. Przykład: sumowanie listy

   sumuj [] = 0
   sumuj (x:xs) = x + sumuj xs
   

4. Implementacja funkcji silnia (niezbyt dobra)

   silnia :: Integer -> Integer
   silnia n = if n <= 1 
           then 1
           else n * silnia (n-1)
   

   Inny wariant (również kiepski)

   fact n | n <= 1 = 1
          | otherwise = n * fact (n-1) 
   

   jeszcze inny wariant (też kiepski)

   fact' 0 = 1
   fact' n = n * fact' (n-1)
   

5. Podstawowe typy: Int, Integer, Float, Double, Char, Bool, ()
6. Funkcja

   myAdd x y = x + 2 * y
   

   ma typ

   myAdd :: Num a => a -> a -> a
   

   Usiłujemy zrozumieć ten fragment a -> a -> a; to jest fragment języka opisu typów; jest równoważmy a -> (a -> a).
7. Currying:
   Odwzorowanie $$ \Phi : A^{B\times C} \to (A^B)^C $$ określone wzorem $(\Phi(f)(c))(b) = f((b,c))$ jest bijekcją.
   PRZEMYŚLCIE To SOBIE DOBRZE !!!

Wprowadzenie do Teorii Kategorii

1. Pojęcie kategorii
2. Przykłady kategorii
   1. Set: obiekty - zbiory; morfizmy - funkcje
   2. Grp: obiekty - grupy; morfizmy - homorfizmy grup
   3. Ustalamy częściowy porządek $(X,\leq)$: obiekty - elementy $X$; strzałki - pary $(x,y)$ takie, że $x\leq y$.
3. Obiekt końcowy w kategorii $\mathcal{C}$: taki obiekt $T$, że dla każdego obiektu $X$ istnieje dokładnie jeden morfizm $f:X\to T$.
4. Obiekt początkowy w kategorii $\mathcal{C}$: taki obiekt $P$, że dla każdego obiektu $X$ istnieje dokładnie jeden morfizm $f:P\to X$.
5. Def. Obiekty $X$ i $Y$ są izomorficzne jeśli istnieją morfizmy $f:X\to Y$ oraz $g:Y\to X$ takie, że $g\circ f = Id_X$ i $f\circ g = Id_Y$
6. Tw. Dowolne dwa obiekty końcowe są izomorficzne. (bez dowodu)
7. Przykład in Set: obiekt końcowy $\{1\}$; obiekt początkowy $\emptyset$.
8. Uwaga: typ $()$ języka Haskell jest odpowiednikiem obiektu końcowego w kategorii typów Haskella (Hask)
9. Uwaga: niektóre kategorie nie mają obiektów końcowych an początkowych

05.03.2019: Listy

Monoidy elementy Teorii Kategorii

1. Pojęcie monoidu
2. Def.MON = kategoria monoidów; morfizmy = homomorfizmy monoidów
3. Listy: List(X) = (X*,[],++)
4. Tw. Dowolne dwa elementy końcowe są izomorficzne
5. [Kategoria dualna]. Mamy kategorię $\mathcal{C}$. Budujemy kategorię $\mathcal{C}^{op}$. Obiekty $\mathcal{C}^{op}$ są obiektami kategorii $\mathcal{C}$. $f:X\to Y$ jest morfizmem w $\mathcal{C}^{op}$ wtedy i tylko wtedy, gdy $f:Y\to X$ jest morfizmem w $\mathcal{C}$. Złożenie morfizmów w $\mathcal{C}^{op}$ definiujemy $f\bullet g = g\circ f$ (gdzie $\circ$ jest złożeniem morfizmów w kategorii $\mathcal{C}$).
6. Obserwacja: obiekty końcowe w $\mathcal{C}$ są obiektami początkowymi w $\mathcal{C}^{op}$; obiekty początkowe w $\mathcal{C}$ są obiektami końcowymi w $\mathcal{C}^{op}$
7. [Metoda dualności] Wniosek. Dowolne dwa elementy początkowe są izomorficzne

Generatory list

1. Podstawowe metody:
   1. Prosta metoda: t = [1,2,3,4], t=[2..20]
   2. Prosta metoda przyrostowa: t = [1,5..20]
   3. Generator t = [f t| t <- xs]
   4. Generator ze strażnikiem: t = [f t| t <- xs, p t]
2. Trójki pitegorejskie

   pyth n = [(a,b,c)| a <- [1..n], b <- [1..a], c <- [1..b],
             a^2 == b^2 + c^2]
   

3. Quick Sort

   qs []     = []
   qs (x:xs) = qs [t| t <- xs, t <= x] ++
               [x] ++
               qs [t| t <- xs, t > x] 
   

   Ten kod łatwo można ulepszyć - to będzie na liście zadań.
4. Kod Cezara i narzędzie do łamania tego kodu oparte na teście statystycznym chi-kwadrat Pearsona : Cesar.hs. Przykład użycia:
   1. Kodowanie: t = encode 3 "Haskell is cool"
   2. Dekodowanie: encode (-3) t
   3. Łamanie kodu: crack t
   (liczba 3 może być zastąpiona dowolną inną liczbą całkowitą - z rozsądnego zakresu)
5. Jak można oprogramować silnię: The Evolution of a Haskell Programmer :--)

12.03.2019: Funktory i lazy evaluation

1. Pojęcie produktu (w języku kategorii)
2. Produkt w kategorii Set: $A\times B = \{(x,y) : x\in A \land y \in B\}$
3. Pojęcie coproduktu (w języku kategorii)
4. Co-produkt w kategorii Set $$ A \oplus B = (A\times\{0\}) \cup (B\times\{1\}) $$
5. Pojęcie funktora między kategoriami. WIKI: Functor

Operator tworzenia list

1. $L(X) = X^*$; $L(f) [x_1,\ldots,x_n] = [f(x_1),\ldots,f(x_n)]$
2. Uwaga (haskell): $L(f) x$ odpowiada map f x (link do kodu z pakietu Prelude:map; przyzwyczajcie się do korzystania z tej strony)
3. Definiujemy $\eta_X (x) = [x]$; mamy: $\eta_X: X \to L(X)$
4. Definiujemy $\mu_X: L(L(X)) \to L(X)$ wzorem $$\mu_X ([L_1,\ldots,L_n]) = L_1++\ldots++L_n$$.
5. Własność 1: $\mu_X \circ \eta_{L(X)} = \mu_X \circ L(\eta_X) = id_{L(X)}$
6. Własność 2: $\mu_X \circ \mu_{L(X)} = \mu_X \circ L(\mu_X)$

Lazy evaluation

1. Przykład:

   Prelude>z = [1..100] :: Int
   Prelude>:sprint z
   z = _
   Prelude>take 5 z
   [1,2,3,4,5]
   Prelude>:sprint z
   z = 1 : 2 : 3 : 4 : 5 : _
   

   Uwaga: tutaj był błąd: było
   Prelude>z = [1..100]
   i nie działało tak jak chciałem.
2. Strumienie (nieskończone listy)

   Prelude>x=[0..]
   Prelude>:take 5 x
   [0,1,2,3,4]
   Prelude>y = map (\n -> n^2) x
   Prelude>:take 5 y
   [0,1,4,9,16]
   

3. Ciąg Fibbonaciego

   f = 0 : 1 : zipWith (+) f (tail f)
   

19.03.2019: Funktory i lambda wyrażenia

26.03.2019: Foldy

02.04.2019: User defined types

09.04.2019: Składanie

30.04.2019: Lemat Yonedy i wstęp do monad

1. Przykłady naturalnych transformacji funktorów.
2. Pojęcie kategorii lokalnie małej.
3. Hom funktor: $\mathcal{Y}_A(X) = Hom(A,X)$; $\mathcal{Y}_A(f) = (\lambda g\to f\circ g)$
4. Lemat Yonedy: Jeśli $\mathcal{C}$ jest lokanie mała, $A$ jest obiektem $\mathcal{C}$ oraz $F: \mathcal{C} \to Set$ jest funktorem, to istnieje bijekcja między $$ Nat(\mathcal{Y}_A, F) $$ oraz $F(A)$. Co więcej, $Nat(\mathcal{Y}_A, F) = \{\eta^{\alpha}: \alpha\in F(A)\}$, gdzie $\eta^{\alpha}(f) = F(f)(\alpha)$.
5. Wniosek. $Nat(X\times\cdots\times X, F) \sim F(\{1,\ldots,n\})$ (po lewej stronie mamy produkt $n$ kopii $X$)
6. Przykład: $Nat(X\times X,X\times X) \sim \{1,2\}\times\{1,2\}$
7. MONADA: Trójka $(L,\eta,\mu)$ taka, że $L$ jest funktorem, $\eta: I \overset{\bullet}{\rightarrow} L$ oraz $\mu : L\circ L \overset{\bullet}{\rightarrow} L$ są naturalnymi transformacjami takimi, że następujące diagramu komutują:
8. Przykład (Lista):
   1. L(X) = [X],
   2. L(f) = map f;
   3. $\eta_X$(x) = [x];
   4. $\mu_X$([X1, ... , Xn]) = X1 ++ ... ++ Xn (= concat [X1, ... , Xn])
9. Pomysł na rozwiązanie problemu sekwencyjnego czytania

   let (x,a) = readInt (0) in 
   let (y,b) = readInt (a) in 
      f(x,y) 
   

   (przekazywanie żetonów).
10. Program "Hello World" w Haskellu przed wprowadzeniem monad do języka:
11. A tak to się robi teraz:

     main = do 
       putStrLn "Hello World"
    

12. Czytanie i wyświetlanie wyniku:

    main = do
      putStr "Podaj liczbę calkowitą : "
      str <- getLine
      let n = read str :: Int
      putStrLn ("Jej szescian to " ++ show(n * n * n))
    

    Szczegóły: na najbliższych wykładach.

Miejsce na twoje notatki

07.05.2019: Monady - I

1. Przykład zanurzenia w struktury o większej liczbie wymiarów: odwzorowania afinicze płaszczyzny są zdefinione wzorem $$ F\left(\begin{bmatrix} x\\y\end{bmatrix}\right) = \begin{bmatrix} a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix} \cdot \begin{bmatrix} x\\y\end{bmatrix} + \begin{bmatrix} b_1\\b_2\end{bmatrix} $$ Implementowane są one (z reguły) w taki sposób $$ \begin{bmatrix} a_{11}&a_{12}&b_1\\a_{21}&a_{22}&b_2\\ 0 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix} x\\y\\1\end{bmatrix} $$
2. Def. Dla monady $(T,\eta,\mu)$ i $f:X\to T(Y)$ definiujemy
   $$f^* = \mu \circ T(f)$$
   Mamy: $f^*: T(X) \to T(Y)$.
3. 1. W1: Jeśli $f:X\to T(Y)$ i $g:Y\to T(Z)$ to $(g^*\circ f^* = (g^*\circ f)^*$
   2. W2: Jeśli $f:X\to T(Y)$ to $f^*\circ \eta_X = f$
   3. W3. $(\eta_X)^* = id_{T(X)}$
4. Operacja BIND: (>>=):: T a -> (a -> T b) -> T b
   $$(tx >\!>= f) = f^*(tx)$$
5. Monada Writer - pierwsze podejście
   1. $W(X) = X \times String$
   2. $W(f)(x,s) = (f(x),s)$
   3. $\eta(x) = (x,"")$
   4. $\mu (((x,s),t)) = (x, t +\!\!+ s)$
   Obliczamy, że $((x,s) >\!>= f) = (f_1(x),s+\!\!+ f_2(x))$, gdzie $f(x) = (f_1(x),f_2(x))$.
   Przerabiamy to na kod Haskella:

   data Writer a = Writer (a,String) deriving Show
   
   instance Functor Writer where
     fmap f (Writer (x,s)) = Writer (f x, s)
     
   instance Monad Writer where
     return x = Writer (x, "")
     (Writer (x,s)) >>= f = let Writer (y,t) = f x in Writer (y, s++t)
     
   instance Applicative Writer where
     pure = return
     fw <*> xw = do f<- fw; x<- xw; return( f x)
   

   UWAGA: $\text{Monada} \subset \text{Applicative} \subset \text{Functor}$.
   Przykład użycia

   half::Int -> Writer Int
   half x = Writer (x `div` 2, "Polowie " ++ show x ++ "; ")
   

   Teraz w GHCI możemy wywołać

   *Main> half 120
   Writer (60,"Polowie 120; ")
   *Main> half 120 >>= half
   Writer (30,"Polowie 120; Polowie 60; ")
   *Main> half 120 >>= half >>= half
   Writer (15,"Polowie 120; Polowie 60; Polowie 30; ")
   

   Inny przykład

   jestPodejrzany :: Int -> Bool
   jestPodejrzany n = (50<=n) && (n<= 55)
   
   dane = [55,11,45,51,22,50,23,1,11,2,3,4,5,6,7,8,55,1,2,3,4,5,6,7,8] :: [Int]
   
   zsumuj :: [Int] -> Writer Int
   zsumuj []     = Writer (0,"")
   zsumuj (x:xs) = zsumuj xs >>= (\y -> if jestPodejrzany x then Writer (x+y,"+") 
                                                            else Writer (x+y, "-"))
   

   Teraz w GHCI możemy wywołać

   *Main> zsumuj dane
   Writer (395,"--------+----------+-+--+")
   

6. Implementacja Monoidu w Haskellu: wiki.haskell.org/Monoid
7. Monada Writer - drugie podejście (uogólniamy String na dowolny monoid)
   1. Implementacja

      import Data.Semigroup
      
      newtype Writer w a = Writer (a,w) deriving Show
      
      instance Functor (Writer w) where
        fmap f (Writer (x,s)) = Writer (f x, s)
        
      instance (Monoid w) => Monad (Writer w) where
        return x = Writer (x, mempty)
        (Writer (x,w)) >>= f = let Writer (y,t) = f x in Writer (y, w `mappend` t)
        
      instance (Monoid w) => Applicative (Writer w) where
        pure = return
        -- fw <*> xw = do f<- fw; x<- xw; return( f x)
        Writer (f, m) <*> Writer (x, n) = Writer (f x, m `mappend` n)
      

   2. Przykład użycia:

      jestPodejrzany :: Int -> Bool
      jestPodejrzany n = (50 <= n) && (n <= 55)
      
      dane = [55,11,45,51,22,50,23,1,11,2,3,4,5,6,7,8,55,1,2,3,4,5,6,7,8] :: [Int]
      
      zsumuj :: [Int] -> Writer (Sum Int) Int
      zsumuj [] = Writer (0,0)
      zsumuj (x:xs) = do 
          zsumuj xs >>= (\y -> 
                            if jestPodejrzany x then Writer (x+y,1) 
                                                else Writer (x+y, 0)
                         )
      

   3. Inny przykład użycia:

      zsumujPlus :: [Int] -> Writer (Sum Int, Sum Int, String) Int
      zsumujPlus [] = Writer (0,(0,0,""))
      zsumujPlus (x:xs) = do 
          zsumujPlus xs >>= (\y -> 
                               if jestPodejrzany x then Writer (x+y,(1,0,"+")) 
                                                   else Writer (x+y,(0,1,"-"))
                             )
      

   4. W ostatnim przykładzie skorzystaliśmy z następującego faktu: jeśli $(M,e,\cdot)$ i $(N,f,\star)$ są monoidami, to struktura $(M\times N,(e,f),\oplus)$, gdzie $(x,y)\oplus(a,b) = (x\cdot a,y\star b)$ jest monoidem.
8. A w ostanich minutach wykładu zabawiliśmy się takim kodem:

   zsumujPlus :: [Int] -> Writer (Sum Int, Sum Int, Dual String) Int
   zsumujPlus [] = writer (0,(0,0,Dual ""))
   zsumujPlus (x:xs) = do 
       zsumujPlus xs >>= (\y ->
           if jestPodejrzany x then writer (x+y,(1,0,Dual "+")) 
                               else writer (x+y,(0,1,Dual "-"))
          )
   

   gdzie Dual M jest monoidem dualnym do monoidu M.

Miejsce na twoje notatki

14.05.2019: Monady - II (notacja do)

1. Własności operacji >>= (bind):
   1. ((tx >>= f) >>= g) = (tx >>= (\x -> f(x) >>= g)) [łączność]
   2. (return x >>= f) = f x [lewa identyczność]
   3. (mx >>= return) = mx [prawa identyczność]
2. Operacja Kleisli'ego (fish): (f >=> g)(x) = f(x) >>= g
3. Tw. ((f >=> g) >=> h) = (f >=> (g >=> h))
   czyli: operacja >=> jest łączna.
4. Tw. (join ttx) = (ttx >>= fmap id)
   czyli odwzorowanie naturalne $\mu$ (join) może być zdefiniowane za pomocą >>=
5. Def. (tx >> ty) = (tx >>= (\_ -> ty))
6. Przykład (listy): ([x1,...,xn] >> a) = a ++ ... ++ a (konkatenacja n kopii listy a = [a1,...,am])
7. Przykład (Maybe): (Nothing >> x) = Nothing, ((Just _) >> x) = x
8. Notacja do
   1. do {x <- tx; expr} == (tx >>= (\x -> do {expr}))
   2. do {let x = w; expr} == (let x = w in do {expr})
   3. do {w; expr} == (w >> do {expr})
   4. do {w} = w
9. Przykład:

   safeInv, safeSqrt :: Float -> Maybe Float
   safeInv x = if x /= 0 then Just (1/x) else Nothing
   safeSqrt x = if x>=0 then Just (sqrt x) else Nothing
   
   f:: Float -> Maybe Float
   f x = do
     y <- Just x
     z <- safeInv x
     safeSqrt z 
   

   Po przetłumaczeniu (odcukrowaniu) kod ten jest równoważny f x = Just x >>= safeInv >>= safeSqrt
10. Trochę bardziej rozbudowany przykład (evaluator prostego języka):

    import qualified Data.Map as M
    
    data Term = N Float 
                | A Term Term 
                | S Term Term 
                | M Term Term 
                | D Term Term
            deriving Show
              
    termA = D (A (N 1)(N 2) ) (M (N 2) (N 3))
    termB = D (A (N 1)(N 2) ) (M (N 2) (N 0))
    
    eval:: Term -> Maybe Float  
    eval (N x)     = Just  x
    eval (A t1 t2) = do x<- eval t1; y<- eval t2; return (x+y)
    eval (S t1 t2) = do x<- eval t1; y<- eval t2; return (x-y)
    eval (M t1 t2) = do x<- eval t1; y<- eval t2; return (x*y)
    eval (D t1 t2) = do x<- eval t1; y<- eval t2; if y==0 then Nothing else return (x/y)
    

11. Jeszcze bardziej rozbudowany przykład (evaluator prostego języka ze zmiennymi):

    data Term =   X String      -- zmienna
                | N Float       -- stała
                | A Term Term   -- add
                | S Term Term   -- substract
                | M Term Term   -- multiply
                | D Term Term   -- divide
    
    termA = D (A (X "x")(X "y") ) (M (X "v") (X "z"))
    termB = D (A (X "x")(N 10 ) ) (M (X "v") (X "w"))
    
    zmienne :: M.Map String Float
    zmienne =  M.fromList [("x",12.0),("y",2.1),("z",3.1),("v",2.0)] 
    
    eval::  M.Map String Float -> Term -> Maybe Float   
    eval z (X x)     = M.lookup x z
    eval z (N x)     = Just x
    eval z (A t1 t2) = do x<- eval z t1; y<- eval z t2; return (x+y)
    eval z (S t1 t2) = do x<- eval z t1; y<- eval z t2; return (x-y)
    eval z (M t1 t2) = do x<- eval z t1; y<- eval z t2; return (x*y)
    eval z (D t1 t2) = do 
      x <- eval z t1; 
      y <- eval z t2; 
      if y==0 then Nothing else return (x/y)
    

Miejsce na twoje notatki

21.05.2019: Monady - III (Writer/Reader)

1. Obliczenia dla $W_M(X) = X\times M$; $W_M(f) (x,m) = (f x, m)$:

     (f,m) <*> (x,y) = (f x, m `mappend` n)
   

2. Przerabiamy to na kod Haskella:

   import Data.Semigroup
   
   newtype Writer w a = Writer {runWriter :: (a,w)} 
   
   instance Functor (Writer w) where
     fmap f (Writer (x,s)) = Writer (f x, s)
   
   instance (Monoid w) => Applicative (Writer w) where
     pure x = Writer (x, mempty)
     Writer (f, m) <*> Writer (x, n) = Writer (f x, m `mappend` n)
     
   instance (Monoid w) => Monad (Writer w) where
     return = pure
     (Writer (x,w)) >>= f = let (y,t) = runWriter(f x) in Writer (y, w `mappend` t)
   

   Uwaga: zastosowaliśmy konstrukcję newtype zamiast data.
3. Dodajemy dodatkowe funkcjonalności do monady Writer. Wprowadzamy nową klase MonadWriter:

   class (Monoid w, Monad m) => MonadWriter w m | m -> w where
     pass   :: m ( a, w->w) -> m a
     listen :: m a -> m (a,w)
     tell   :: w -> m ()
     writer :: (a,w) -> m a
   

   (m->w oznacza, że z monady m wynika jednoznacznie typ monoidu w) i tak oprogramowujemy instancję Writera:

   instance (Monoid w) => MonadWriter w (Writer w) where
     pass   (Writer ((a,f),w)) = Writer (a, f w)
     listen (Writer (a, w))    = Writer ((a,w),w)
     tell   w                  = Writer ((),w)
     writer (a,w)              = Writer (a,w)   
   

   Aby do zrobić, w nagłowku pliu z kodem musimy dodać następujące polecenia dla kompilatora:

   {-# LANGUAGE FunctionalDependencies #-}
   {-# LANGUAGE FlexibleInstances      #-}
   

4. Przykładowy kod

   import Control.Monad.Writer
   
   half :: Int -> Writer String Int
   half x = do
           tell ("Przepolowilem " ++ show x ++ "! ")
           return (x `div` 2)
   

   i przykłady użycia:

   *Main> runWriter $ half 120
   *Main> runWriter $ half 120 >>= half
   *Main> runWriter $ half 120 >>= half >>= half
   

5. Własności monady Writer: definiujemy funkcję $\pi:X\times M \to X: (x,m)\to x$ (projekcja na pierwszą oś). Jeśli $f:X \to W_M(Y)$, $g:Y \to W_M(Z)$, $h:Z \to W_M(U)$ to $$ \pi\large( (x,m) \gt\!\gt= f \gt\!\gt\!= g \gt\gt= h\large) = \large((\pi\circ h) \circ (\pi\circ g) \circ (\pi \circ f)\large)(x) $$ Uwaga: Writer jest wyjątkową monadą; mamy naturalną transformację $\pi: W_M \Rightarrow I$ taką, że $\pi\circ \eta = \text{id}$.
6. Monada Reader:
   1. $R_A(X) = X^A$;
   2. $R_A (f:X\to Y) = (\phi \to f\circ\phi)$
   3. $\eta(x) = (\lambda a \to x)$;
   4. $\mu(\Phi) = (\lambda a \to (\Phi(a))(a))$
   5. Po prostych obliczeniach otrzymujemy: $$(\phi \gt\!\!\gt\!= f) = (\lambda a \to f (\phi(a))(a))$$
7. Szczegóły implementacji

   instance MonadReader p (Reader p) where
     ask        = Reader id
     reader     = Reader
     ....
   

8. Przykład użycia:

   import Control.Monad.Reader
   import Data.Char  (toLower)
     
   cleanStr :: String -> String;
   cleanStr x =  map toLower ( unwords . words  x )
   
   cleanFirstStr :: Reader (String,String) String
   cleanFirstStr = do
     (x, _) <- ask
     return ( cleanStr x )
   
   cleanSecondStr :: Reader (String,String) String
   cleanSecondStr = do
     (_,y) <- ask
     return ( cleanStr y )
   
   compStr :: Reader (String,String) Bool
   compStr = do
     a <- cleanFirstStr
     b <- cleanSecondStr
     return (a==b)
   
   -- użycie: (runReader compStr) ("Ala   ma   kota", "Ala ma KOta") 
   

Miejsce na twoje notatki

28.05.2019: Monady - IV

1. Złożenie horyzontalne naturalnych transformacji: jeśli $\alpha:F \Rightarrow G$ oraz $\beta:K \Rightarrow L$ to $$ (\beta\star\alpha)_X = \beta_{G(X)} \circ K (\alpha_X) $$
2. Zrobiliśmy (było trochę roboty) de-sugaryzację kodu z poprzedniego wykładu. Pokazaliśmy, że cały kod jest równoważny następującemu kodowi

   cleanStr :: String -> String;
   cleanStr x =  map toLower ( unwords . words  x )
   
   compStr:: String -> String -> Bool
   compStr a b = cleanStr a == cleanStr b
   

3. Zaczęliśmy dobierać się do monady State. Ustalamy zbiór S.
   1. Rozważać będziemy przyporządkowanie $S(X) = (X\times S)^S$ (jak zrobić z tego funktor - później)
   2. Dla $f:X\times S \to Y\times S$ definiujemy $f^c: X \to (Y\times S)^S$ wzorem $f^c(x) = \lambda s \to f((x,s))$
   3. Dla $f:X \to (Y\times S)^S$ definiujemy $f^u: X \times S \to (Y\times S)$ wzorem $f^u((x,s)) = (f(x))(s)$
   4. Mamy $(f^c)^u = f$ oraz $(g^u)^c = g$
   5. Dla $\alpha \in (X\times S)^S$ i $f:X\to (Y\times S)^S$ definiujemy $$ (\alpha \BIND f) = f^u \circ \alpha $$
   6. Definiujemy $\eta_X = (id_{X\times S})^c$; czyli $\eta_X(x) = (\lambda s\to(x,s))$
   7. Fakt 1: $(\alpha \BIND \eta) = \alpha$
   8. Fakt 2: $(\eta(x) \BIND f) = f(x)$
   9. Fakt 3: $((\alpha \BIND f) \BIND g) = (\alpha \BIND (\lambda x \to f(x) \BIND g))$
   10. ZATEM zanurzenie $\eta$ i operacja $\BIND$ spełniają prawa monady. Na następnym wykładzie będziemy te rozważania kontynuować i zrobimy z przyporządkowania $S$ monadę.

Miejsce na twoje notatki

04.06.2019: Monady - IV

1. Zakładamy, że mamy przyporządkowanie $M:\mathcal{C}\to\mathcal{C}$, naturalne przyporządkowanie $\eta:I \to F$ oraz $\BIND$ spełniające prawa monadyczne.
   1. Definiujemy $M(f:X\to Y) (mx)= (do \{x \leftarrow mx; return (f x)\}) = mx \BIND (\lambda x \to \eta(f(x)))$. Pokazaliśmy, że w ten sposób zrobiliśmy z przyporządkowania $M$ funktor.
   2. Definiujemy $\mu(mmx) = (do\{mx\leftarrow mmx; mx\}) = mmx \BIND id$.
   3. Pokazaliśmy, że trójka $(M,\eta,\mu)$ jest monadą.
   4. Pokazaliśmy, że jeśli za pomocą trójki $(M,\eta,\mu)$ zdefiniujemy operację BIND, to otrzymamy tę samą operację od której zaczęliśmy.
2. State monad: obliczamy S(f:X\to Y). Otrzymaliśmy $$ S(f:X\to Y) (\alpha) = (\lambda s \to \text{ let } (x,t) = \alpha(s) \text{ in } (f(x) ,t)) $$
3. Implementacja monady state w Haskellu

   {-# LANGUAGE FunctionalDependencies #-}
   {-# LANGUAGE FlexibleInstances #-}
   
   newtype State s a = State {runState::s -> (a,s)}
   
   instance Functor (State s) where
       fmap f st = State (\s -> let (x,t) = runState st s in (f x,t))
      
   instance Monad (State s) where
       return x  = State (\s -> (x, s))
       sx >>= f  = State $ \s -> 
                             let (x, t) = runState sx s
                             in runState (f x) t
                             
   instance Applicative (State s) where
       pure = return
       fS <*> xS = do f<- fS; x<- xS; return (f x)
   
   class Monad m => MonadState s m | m -> s where
       get :: m s       -- | Replace the state inside the monad.
       put :: s -> m () -- | Embed a simple state action into the monad.
       state :: (s -> (a, s)) -> m a
    
   instance MonadState s (State s) where
       get     = state (\s -> (s, s))
       put s   = state (\_ -> ((), s))
       state f = State f   
   

4. Przykład: myślimy o funkcji f: (Float,Int) -> (Float,Int) określonej wzorem $$ f(x,s) = \begin{cases} (\sqrt{|x|},s+1) &: s \lt 5 \\ (x+1,s+1) &: x\geq 5\end{cases} $$ Robimu currying tej funkcji i zamieniamy to w kod

   fnc :: Float -> State Int Float
   fnc x = state ( \s -> if s < 5 then (sqrt (abs x), s+1) else (x+1, s+1) )  
   

   Przykład użycia (runState ((return 10.0)>>= fnc >>= fnc)) 0
5. Bawimy się z funkcją Collatza. Zaczynamy od wersji licznikowej:

   import Control.Monad.State
   
   oneStepCollatz :: Int -> Int
   oneStepCollatz n = if mod n 2 == 0 
          then div n 2
          else 3*n + 1
                          
   collatz :: Int -> State Int Int                       
   collatz n = if n <= 1 
            then return 1
            else do 
              k <- collatz (oneStepCollatz n)
              state (\s -> (k,s+1))
   

   Uwaga: to mogliśmy zrobić za pomocą monady Writer. Ale teraz modyfikujemy: pozwalamy iterować tylko ograniczoną liczbę razy:

   lazyCollatz :: Int -> State Int Int                       
   lazyCollatz n = if n <= 1 
             then return 1
             else do 
               let stan = lazyCollatz (oneStepCollatz n)
               state (\s -> let (y,t)= (runState stan) s in 
                            if t>0 then ( y, t-1) 
                                   else (-1, t)
                     )
   

   Teraz mamy

   *Main> runState (lazyCollatz 96) 100
   (1,88)
   

   ale dla liczby 97 odmawia obliczeń; mamy bowiem

   *Main> runState (lazyCollatz 97) 100
   (-1,0)
   

6. Monoid w języku teorii kategorii: gdzie $(M,e,\star)$ jest monoidem, $I$ = końcowy obiekt w kategorii Set, $\eta:I \to M$ jest dana wzorem $\eta () = \text{const}_e$ oraz $\mu(x,y)= x\star y$.

Miejsce na twoje notatki

11.06.2019: Monady - V

1. Przekształciliśmy równania algebraiczne monad w diagramy definiujące monoidy. Stwierdziliśmy, że monada jest monoidem w klasie Endo(Set) (endofunktorów klasy Set), gdzie iloczynem tensorowym jest złożenie, identycznością transformacja naturalna $\eta$ zaś działaniem binarnym jest transformacja $\mu$ (tu będzie obrazek)
2. Porównanie monad - I
   1. Listy: $\eta(x) = [x]$
   2. Reader: $\eta(x) = (\lambda a \to x)$
   3. Writer: $\eta(x) = (x,e)$
   4. State: $\eta(x) = (\lambda s \to (x,s))$
3. Porównanie monad - II
   1. Listy: $([x_1,\ldots,x_n] \BIND f) = (f x_1) ++ \ldots ++ (f x_n)$
   2. Reader: $(rx \BIND f) = (\lambda a \to (f (rx(a))) a)$
   3. Writer: $((x,m)\BIND (f_1,f_2)) = (f(x_1), m\star f_2(x))$
   4. State: $(sx \BIND f) = (\lambda s \to \text{ let } (x,t) = sx(s) \text{ in } (f(x))(t))$
4. STRESZCZENIE: średnik w do{x<-mx; f x} jest (w odróżnienu od klasycznych języków programowania) średnikiem programowalnym
5. Lifting and friends:
   1. LiftM

      liftM :: (Monad m) => (a -> b) -> (m a -> m b)
      liftM f mx = do {x<- mx; return (f x)}    
      

      Proste obliczenia pokazują, że liftM = fmap. To jest efekt pewnych błędów historycznych.
   2. LiftM

      liftM2 :: (Monad m) => (a -> b -> c) -> (m a -> m b -> m c)
      liftM2 f mx my = do {x<- mx; y <- my; return (f x y)}    
      

      Przykłady: liftM2 (+) [1,2] [10,20] => [11,21,12,22],
      liftM2 (+) (Just 3) (Just 2) => Just 5
      Twierdzenie. liftM2 f (return x) (return y) = return (f x y)
   3. filterM

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

      Przykład: (filterM (\_ -> [True,False]) [1,2,3]) => wszystkie "podzbiory" [1,2,3]
6. IO (X) = State OuterWorld X
   jest to wariant monady typu State z brakiem bezpośredniego dostępu do zbioru stanów OuterWorld. Tu będzie obrazek.
7. Przykład:

   main :: IO ()
   main = do
       putStr "Podaj imie "       -- :: IO ()
       s <- getLine            -- :: IO String 
       putStrLn ( "Witaj " ++ s ) -- :: IO ()
   

Miejsce na twoje notatki