Strona główna Moje zajęcia

2018/19: Programowanie funkcyjne

Wykład przeznaczony jest dla studentów I stopnia Informatyki na WIT. Odbywa się w czwartki w godz. - w sali 29/D-1.

Zasady zaliczania kursu

Zaliczenie tego kursu polega na otrzymaniu zaliczenia z laboratorium. Nie ma egzaminu końcowego. Będą trzy sprawdziany. Dwa pierwsze po 45 minut. Ostatnie 90 minut. Dwa z nich będą tylko charakter programistyczny. Ostatnie będzie miało charakter programistyczny i teoretyczny.
Terminy:

  1. 24-28.10.2022 (praca w GHCi; głównie rekursja)
  2. 21-28.11.2022 (typami, klasy typów),
  3. na ostatnich labach (podstawowe monady; elementy teorii kategorii)
Kolokwia będą oceniane w skali 0-10 pkt. Ponadto będzie można zdobyć 10 punktów za aktywność. Progi ocen:
  1. 15 - 19 : dost
  2. 20 - 24: dost+
  3. 25 - 29: db
  4. 30 - 34: db+
  5. 35 - 40: bdb
Ocena 5.5 = musi być 5.0 z kolokwium+aktywność oraz ustne zaliczenie (rozmowa za mną).

Literatura

$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\CC{\mathbb{C}} \def\NN{\mathbb{N}} \def\BIND{\,>\!>\!=\,} \newcommand{\span}[1]{\mathrm{span}(#1)} \newcommand{\IS}[2]{\langle\,#1,#2\rangle} \newcommand{\sgn}[1]{\mathrm{sgn}(#1)} $

Zagadnienia omówione na wykładzie

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

Wszystkie przestawione tutaj wersje są "lipne". Wkróce poznamy lepsze rozwiązanie
  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
Oto jest jej typ
mymap :: (t -> a) -> [t] -> [a]
Zauważyliśmy, że jeśli $f::[a] \to [b]$ i $g::[b]\to[c]$ to $$ (\text{map } g) \circ (\text{ map } f) = \text{map } (g\circ f) ~ $$

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

Źródła programów, które pokazywałem na wykładzie:
  1. SimpleIO_00.hs
  2. SimpleIO_01.hs
  3. SimpleIO_02.hs
  4. guessANumber.hs
  5. zapalki.hs
  6. zapalki1.hs
  7. zapalkiW.hs
Notatki na temat "A monad is a monoid in the category of endofunctors, what's the problem?" pojawią się tutaj około 24 grudnia.

Strona główna Moje zajęcia