06.10.2022: Wstęp

1. ...
2. Def. Relacja $R \subseteq X\times X$ jest ufundowana jeśli nie istnieje ciąg $(x_n)_{n\in\NN}$ elementów zbioru $X$ taki, że $$ (\forall n\in \NN)( (x_{n+1},x_n) \in R) $$
3. Tw [O Rekursji] Załóżmy, że $R$ jest relacją ufundowaną na zbiorze $X$ oraz, że $F:V\times X \to V$ jest funkcją. Istnieje wtedy funkcja $f:X\to V$ taka, że $$ (\forall x\in X) (f(x) = F(f\restriction prec(x),x))~, $$ gdzie $prec(x) = \{y \in X: (y,x) \in R\}$.
4. Def. 2 - arnym curryingiem nazywamy odwzorowanie $\text{curry}: C^{A\times B} \to (C^{B})^{A}$ określone wzorem
   $$\large(\text{curry}(f)(a)\large)(b) = f((a,b))$$
5. Fakt: Funkcja curry jest bijekcją.

13.10.2022: Wprowadzenie do Haskell'a

Kilka kodów omówionych na wykładzie:

Kilka wersji funkcji silnia

1. Z wykorzystaniem konstrukcji if ... then ... else ...:

   fact01 n = if n == 0 then 1 else n * fact01 (n-1)
   

2. Z wykorzystanie "pattern-matching"

   fact02 0 = 1
   fact02 n = n * fact02 (n-1)
   

3. Z wykorzystaniem "case expression"

   fact03 n | n<=0 = 1
            | otherwise = n * fact03 (n-1)
   

4. Z wykorzystaniem "case of expression"

   fact04 n = case n of
     0 -> 1
     n -> n * fact04 (n-1)
   

Trzy wersje procedury Quick Sort

1. Wersja "czysta"

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

2. Wersja z wykorzystaniem "where"

   qs02 [] = []
   qs02 (x:xs) = left ++[x] ++ right
     where left  = qs02 [t|t<- xs,t<=x]
           right = qs02 [t|t<-xs,t>x]
   

3. Wersja z wykorzystaniem "let"

   qs03 [] = []
   qs03 (x:xs) = let left  = qs03 [t|t<- xs,t<=x]
                     right = qs03 [t|t<-xs,t>x]
                 in left ++[x] ++ right
   

Implementacja funkcji map

mymap f [] = []
mymap f (x:xs) = f x : mymap f xs

mymap :: (t -> a) -> [t] -> [a]

20.10.2022: Listy

1. Funkcja foldr
2. Co możemy zdefiniować za pomocą foldr:
   1. sum = foldr (+) 0
   2. product = foldr (*) 1
   3. and = foldr (&&) True
   4. or = foldr (||) False
   5. concat = foldr (++) []
3. Zwarta definicja silnii: fact n = product [1..n]
4. Funkcja foldl
5. Implementacja funkcji reverse działająca w czasie liniowym:

   reverse = foldl (flip (:)) []
   gdzie
   flip f = (\x y -> f y x)
   

6. Operacje na nieskończonych listach
7. Funkcja zip oraz ziWith
8. Jeden ze sposobów numerowania elementów listy

   enum xs = zip [1..] xs
   

9. Jedna z metod zdefiniwania ciągu Fibonacciego:

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

10. Elementy Teorii Kategorii
    1. Definicja kategorii (stosujemy terminologię $ob(\mathcal{C})$, $morph(\mathcal{C})$, $dom(f)$, $codom(f)$)
    2. Przykłady: Set, Grp (kategoria grup)
    3. Każdy częściowy porządek można traktować jako kategorię
    4. Pojęcie elementu końcowego.

27.10.2022: Listy

1. Lambda wyrażenia - dr Maciej Gębala
2. Pojecie funktora: odwzorowanie $F$ jest funktorem z kategorii $\mathcal{C}$ do kategorii $\mathcal{D}$ jeśli $$F: ob(\mathcal{C}) \cup morph(\mathcal{C}) \to ob(\mathcal{D}) \cup morph(\mathcal{D})~,$$ $F\restriction ob(\mathcal{C}):ob(\mathcal{C})\to ob(\mathcal{D})$, $F\restriction morph(\mathcal{C}):morph(\mathcal{C})\to morph(\mathcal{D})$ o następujących własnościach:
   1. (zgodność) jeśli $f:X\to Y$ to $F(f):F(X)\to F(Y)$
   2. (zachowanie złożenia) jeśli $f:X\to Y$ i $g:X\to Z$ (w $\mathcal{C}$), to $F(g\circ f) = F(g)\circ F(f)$ (w $\mathcal{D}$)
   3. (zachowanie identyczności) $F(id_X) = id_{F(X)}$
3. Przykład: $L(X) = [X]$, $L(f) xs = map f xs$
4. Przykład programu wyznaczającego najczęściej występujące słowa w łańcuchu

   {- 
     Konstrukcja funkcji wyznaczającej najczęściej występujące 
     słowa w tekście
   --}
   
   import Data.List(group, sort, sortBy)
   import Data.Char(toLower)
   
   dopuszczalne = [' ']++['a'..'z']
   
   stopWords    = ["a","an","and","are", "at", "as","all",
                   "be", "by", "do", "it", "in", "no", "ll", 
                   "so", "s", "o", "or", "t", "th", "this","that","the","thy",
                   "i", "it", "he", "his", "me",
                   "is","to","thou","tis",
                   "you","your","our",  
                   "we","will","was"]  -- dosyć przypadkowe
   
   txt2Lower = map toLower
   
   oczyscZnaki = map (\c -> if elem c dopuszczalne then c else ' ') 
   
   oczyscSlowa = filter (\slowo -> not(elem slowo stopWords))
    
   zlicz = map (\l -> (head l, length l))
   
   posortuj = sortBy (\x y -> compare (snd y) (snd x))  
   
   przeksztalc =  posortuj 
                  . zlicz 
                  . group -- grupuje sąsiednie elementy :: [a] -> [[a]]
                  . sort -- aby poprawnie móc zastosować group
                  . oczyscSlowa
                  . words
                  . oczyscZnaki 
                  . txt2Lower  
   
   mostFrequent n xs = map fst (take n ( przeksztalc xs))
   
   {- 
     Po raz pierwszy na wykładzie komunikujemy się ze światem zewnętrznym.
     Omówimy to w przyszłości dokładniej
   -}
   main = do
     txt <- readFile "hamlet.txt"
     putStrLn (show (mostFrequent 50 txt))
   

   Link do pliku hamlet.txt
5. Modelowanie skończonego automatu niedeterministycznego
   Taka niezbyt uniwersalna realizacja:

   {- 
     Automat niedeterministyczny rozpoznając język {a,b}^*a{a,b}{a,b}{a,b},
     czyli "a" ma być na czwartym miejscu od końca
   -}
   
   import Data.List
   {- funkcja przejścia -}
   δ :: Int -> Char -> [Int]
   δ 'a' 0 = [0,1]
   δ 'b' 0 = [0]
   δ  _  1 = [2]
   δ  _  2 = [3]
   δ  _  3 = [4]  -- stan końcowy
   δ  _  4 = [5]  -- błąd
   δ  _  _ = [5]
   
   {-- podniesienie funkcji przejscia na zbiory stanów -}
   δS :: [Int] -> Char -> [Int]
   δS ss c = nub $ concat $ map (\x -> δ c x) ss
   
   {-- symulacja obliczeń --}
   oblicz :: String -> [Int]
   oblicz cs = foldl δS [0] cs
   
   {-- funkcja akceptująca -} 
   accept cs = elem 4 (oblicz cs)
   
   -- przekształcenie w DFA
   
   {-
     accessibleFrom stany : 
       input: lista list stanów [[Init]]
       output: input ++ lista list stanów do których można dojść ze stanów z listy input 
     ważna własność: stany są sublistą (accessibleFrom stany), czyli, mniej więcej, 
            xs subseteq aF(xs)  
     Uwaga 1. aby ograniczyć eksplozję liczby stanów stosujemy funkcję nub
     Uwaga 2. nakładamy funkcję sort aby można było zastosować metodę fix punktu w następnej funkcji
   -}  
   
   accessibleFrom stany = sort $ nub $ map (\st -> δS st 'a') stany ++ map (\st -> δS st 'b') stany ++ stany
   
   {-
     wyznaczStany x === najmniejszy punkt stały odwzorowania y --> accessibleFrom y
                        większy lub równy x  
   -}
   
   wyznaczStany x | x == fx   = x
                  | otherwise = wyznaczStany fx
                  where fx = accessibleFrom x       
   
   wyznaczPrzejscia xs = [(x,a,y) | x <- xs, y <- xs , a <- ['a','b'], δS x a == y]              
   
   dFA = wyznaczPrzejscia $ wyznaczStany [[0]]
   

03.11.2022: Typy

1. Składanie funktorów: jeśli $F:Set \to Set$ i $f:X\to Y$, to $F(f): F(X) \to F(Y)$, $F(F(f)): F(F(X)) \to F(F(Y))$; F(f) odpowiada odwzorowaniu fmap f, zaś F(F(f)) odpowiada (map.map) f. Przykłady:

   (map.map) f [[x,y],[u,w,v]] = [[f x, f y], [f u, f w, f v]]
   (map.map) f ((x,y),(u,w)) = ((f x,f y),(f u, f v))
   

2. Często stosowany skrót na map

     f <$> xs  =  map f xs
   

3. Operacja włożenia w funktor: $\eta: X \to F(X)$.

   Listy :  η(x) = [x]
   Produkt: η(x) = (x,x)
   Maybe:   η(x) = Just x
   

4. Operacja spłaszczanie iteracji funktora: $\mu: F(F(X)) \to F(X)$.

   Listy : μ [L1, L2, ... , Ln] = L1 ++ L2 ++ ... ++ Ln
   Produkt:μ((x,y),(u,w)) = (x,w)
   Maybe:  μ(Just(Just x)) = Just x;
           μ(Just Nothing)) = Nothing
           μ(Nothing) = Nothing
   

5. Typy wyliczeniowe

   data Kolory = Green | Orange | Red deriving Show
   
   data DOW = Pon|Wto|Sro|Czw|Pia|Sob|Nie deriving (Show, Read, Eq, Ord, Enum, Bounded)
   

   Zwróćcie uwagę na rolę przypisania typu DOW do kilku klas. Przetestujcie w GHCI polecenia
   >[Wto .. Pia], > minBound :: DOW
6. Typy parametryczne

   data Punkt a = Punkt a a deriving ({-Show, -}Eq, Ord) 
   
   instance (Show a) => Show (Punkt a) where
     show (Punkt x y) = show (x,y)
     
   instance Functor Punkt where
     fmap f (Punkt x y) = Punkt (f x) (f y)
   

   Sami zaimplementowaliśmy funkcję show, bo nie byliśmy zadowoleni z jej domyślnej implementacji. Zaliczyliśmy następnie konstruktor Punkt do klasy Functor. Zrealizowaliśmy więc w języku Haskell odpowiednik funktora $P(X) = X\times X$, $P(f) (x,y) = (f(x), f(y))$.
7. Typy rekurencyjne

   data BinTree a = Leaf a | Inner (BinTree a) (BinTree a) deriving(Eq)
     
   instance (Show a) => Show (BinTree a) where
     show (Leaf x)     = show x
     show (Inner lt rt) =  "<" ++ show lt ++ "|" ++ show rt ++ ">"
   
   {- mytree: do testów --}  
   mytree = Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 5)
   
   {- Zaliczamy BinTree do klasy Funktor --}
   instance Functor BinTree where
     fmap f (Leaf x) = Leaf (f x)
     fmap f (Inner lt rt) = Inner (fmap f lt) (fmap f rt)
   
   {-- Zaliczmy BinTree do klasy Foldable --}
   instance Foldable BinTree where 
     foldr f base (Leaf x) = f x base
     foldr f base (Inner lt rt) = foldr f base' lt
            where base' = foldr f base rt 
   

   Funkcja foldr (\x acc -> acc+1) 0 zlicza liczbę liści. Funkcja foldr (\x acc -> acc+x) 0 sumuje liście.
8. Samodzielnie implementujemy konstruktora Maybe, ale aby nie było kolizji nazw nazywamy go MB i trochę sztuczne nazwy "Dokładnie" i "Nic"

   data MB a = Dokladnie a | Nic deriving (Eq, Show, Ord)
   
   instance Functor MB where
     fmap _ Nic = Nic
     fmap f (Dokladnie x) = Dokladnie (f x)
   
   returnMB x = Dokladnie x
   

9. A teraz przeskakujemy do stosowania typu Maybe a

   safeHead :: [a] -> Maybe a
   safeHead [] = Nothing
   safeHead (x:xs) = Just x
   
   safeTail []     = Nothing
   safeTail (x:xs) = Just xs
   
   safeSqrt x = if x < 0  then Nothing else return (sqrt x)
   safeLog  x = if x <= 0 then Nothing else Just (log x)
   

10. Omawiamy składanie w monadach List i Maybe

    (>>=) :: M a -> (a -> M b) -> M b
    (mx >>= f) = μ(F(f) mx)
    

03.11.2022: Typy

1. Prawa monad zapisane w języku return i >>= (bind):

       (return x) >>= f     =   f x
       mx >>= return        =   mx
       (mx >>= f) >>= g     =   mx >>= (\x -> (f x) >>= g) 
   

1. Prawa monad zapisane w języku return i >=> (fish; then):

       return >=> f        =   f 
       f >=> return        =   f
       (f >=> g) >=> h     =   f >=> (g >=>= h) 
   

2. Twierdzenie: Obie definicje są równoważne.
   
   • (f >=> g) = (\x -> ((f x) >>= g))
   • ((mx) >>= g) =   (((const mx) >=> g) ())
3. Desugaryzacja do:

   Wyrażenie	Tłumaczenie
   do e	e
   do { e; stmts }	e >> do { stmts }
   do { v <- e; stmts }	e >>= (\v -> do { stmts })
   do { let decls; stmts}	let decls in do { stmts }

   gdzie (>>):: m a -> m b -> m b jest zdefiniowana wzorem (mx >> my) = (mx >>= (\_ -> my)).

24.11.2022: Monady : I

1. Funkcja sequence::[M a] --> M [a]
2. Monada Writer
   1. Pierwsza przymiarka: Writer0.hs
   2. Piersze ulepszenie: Writer1.hs
   3. Dodanie funkcjonalności: Writer2.hs
   4. Korzystamy z haskelowego Writer'a: Writer3.hs
3. c.d.n.

01.12.2022: Monady /h3>

Monada State

1. Samodzielna implementacja: State1.hs
2. Korzystamy z haskelowego State: State2.hs

Podstawowe funkcje monadyczne

1. (do x <- mx; return f x) ≡ (fmap f mx)
2. Def: (liftM2 (op) mx1 mx2) = (do {x1 <- mx1; x2 <- mx2; return (x1 op x2)})
   typ: liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
   • (liftM2 (+) (Just 2) (Just 3)) = Just 5
   • (liftM2 (+) [1,2,5] [1,2,5]) = [2,3,6,3,4,7,6,7,10]
3. Def. (sequence [mx1,...,mxn]) = (do{ x1 <- mx1;...; xn <- mxn; return [x1,x2,...,xn]})
   typ: sequence :: (Monad m) => [m a] -> m [a]
   • sequence [Just 2, Just 3, Just 5] = Just [2,3,5]
   • sequence [[1,2],[3,4],[10,11]] =
     [[1,3,10],[1,3,11],[1,4,10],[1,4,11],[2,3,10],[2,3,11],[2,4,10],[2,4,11]]
4. Def. mapM f = sequence . (map f)
   typ: mapM :: (Monad m) => (a -> m b) -> [a] -> m [ b]
   • (mapM (\x -> Just x) [1,2,3]) = (Just [1,2,3])
   • mapM (\_ -> [1,2]) [1,2,3] = [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]
5. filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

     filterM  p (x:xs) = do
       cond <- p x
       ys <- filterM p xs
       return( if cond then (x:ys) 
               else ys )    
   

   • (filterM (\x -> Just(x>2)) [1..5]) = (Just [3,4,5])
   • filterM (const [False,True]) [1..3] =
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

08.12.2022: Monady oraz Monada IO

1. SimpleIO_00.hs
2. SimpleIO_01.hs
3. SimpleIO_02.hs
4. guessANumber.hs
5. zapalki.hs
6. zapalki1.hs
7. zapalkiW.hs