Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b36fup [2025/05/25 11:10] – mistrjirkastatnice:bakalar:b4b36fup [2026/06/06 14:57] (current) – [Church‑Rosserova věta] knedl1k
Line 1: Line 1:
 +[[https://intranet.fel.cvut.cz/cz/education/bk/predmety/47/03/p4703006.html|B4B36FUP]] [[https://aicenter.github.io/FUP/|Webové stránky předmětu]]
 +
 ====== Funkcionální jazyky a jejich vlastnosti. Lambda kalkulus, iterativní konstrukty a rekurze. ====== ====== Funkcionální jazyky a jejich vlastnosti. Lambda kalkulus, iterativní konstrukty a rekurze. ======
   - Čisté funkce (pure functions), jejich výhody a nevýhody.   - Čisté funkce (pure functions), jejich výhody a nevýhody.
Line 10: Line 12:
   - Typové třídy Functor, Applicative functor, Monad a jejich použití.   - Typové třídy Functor, Applicative functor, Monad a jejich použití.
  
-===== Funkcionální jazyky a jejich vlastnosti. Lambda kalkulus, iterativní konstrukty a rekurze. ===== +===== Čisté funkce =====   
-===== Čisté funkce (pure functions), jejich výhody a nevýhody. ===== +**Čisté funkce (pure functions), jejich výhody a nevýhody.**   
-===== Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion). ===== +Čistá funkce je taková, která  
-===== Reprezentace seznamů a stromů ve Scheme/Racketu. ===== +(1) vrací vždy stejný výsledek pro stejné hodnoty argumentů a  
-===== Víceřádové funkce (higher-order functions), příklady, currying a částečně vyhodnocené funkce, levý a pravý fold. ===== +(2) nevytváří vedlejší efekty – tedy nečte ani nemění nic mimo svůj vnitřní rozsah; nesahá na globály, neloguje, nedělá I/O a ani nemutuje objekty předané referencí či pointerem. 
-===== Funkční (neboli lexikální) uzávěry, příklady. ===== +==== Výhody čistých funkcí ==== 
-===== Lambda kalkulus, alfa-konverze, beta-redukce, evaluační strategie (normal a applicative), normální forma, Church-Rosserova věta, Y-combinator. ===== +<markdown> 
-===== Algebraické datove typy (ADT) v Haskellu, příklad rekurzivního ADT. ===== +- **Determinismus**: Pro stejné vstupy vždy vrací stejné výstupy, což usnadňuje testování a ladění. 
-===== Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu. ===== +- **Snadná kompozice**: Čisté funkce lze snadno kombinovat a vytvářet složitější funkce. 
-===== Typové třídy Functor, Applicative functor, Monad a jejich použití. =====+- **Lepší optimalizace**: Kompilátory mohou lépe optimalizovat čisté funkce, protože znají jejich chování. 
 +- **Paralelizace**: Čisté funkce lze snadno spouštět paralelně, protože nemají vedlejší efekty, které by mohly způsobit konflikty mezi vlákny. 
 +- **Možnost memoizace**: Čisté funkce mohou být snadno ukládány do mezipaměti (cache), což zvyšuje výkon při opakovaném volání s těmi samými argumenty. 
 +</markdown> 
 + 
 + 
 +==== Nevýhody čistých funkcí ==== 
 +<markdown> 
 + 
 +- **Výkon**: Čisté funkce mohou být méně výkonné, protože nemohou využívat vedlejší efekty.  
 +- **Složitost**: Některé úlohy mohou být obtížné nebo neefektivní řešit čistými funkcemi, například operace s I/O nebo stavem. 
 +- **Overhead s zachováváním stavu**: Čisté funkce často vyžadují předávání stavu jako argumentů, což může vést k horšímu výkonu a složitějšímu kódu. 
 + 
 + 
 +</markdown> 
 + 
 +===== Rekurze =====   
 +**Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion).**   
 + 
 +Rekurzivní funkce je funkce která volá sama sebe. 
 + 
 +<code scheme> 
 +(define (fact n) 
 +  (cond ((= 0 n) 1) 
 +    (#t (* n (fact (- n 1)))) 
 +  ) 
 +) 
 +</code> 
 + 
 +Typy rekurzí: 
 +  * tail recursion - rekurzivní krok se volá na konci funkce, rekurze se nevětví 
 +  * head recursion - rekurzivní krok se volá na začátku funkce, nic se před ním neprovádí, rekurze se nevětví 
 +  * tree recursion - voláme samotnou rekurzi vícekrát 
 +  * nested recursion - voláme rekurzi jako argument v jiné rekurzi 
 +  * přímá / nepřímá rekurze - funkce volá sama sebe / volá jinou funkci která volá zpět funkci 
 + 
 +Tail recursion by například vypadala (sečtení listu): 
 +<code scheme> 
 +(define (sum list [acc 0]) 
 +  (if (empty? list)  
 +    acc 
 +    (sum (cdr list) (+ acc (car list))) 
 +  ) 
 +) 
 +</code> 
 + 
 +Tree rekurze (sečtení stromu): 
 +<code scheme> 
 +(struct node (val kids) #:transparent) 
 +(struct leaf (val) #:transparent) 
 + 
 +(define (value t) 
 +  (match t 
 +    [(leaf x) x] 
 +    [(node x kids) x] 
 +  ) 
 +) 
 + 
 + 
 +(define (tree-sum tree) 
 +  (if (leaf? tree) 
 +    (value tree) 
 +    (+  
 +      (val tree)  
 +      (sum 
 +        (map tree-sum (kids tree)) 
 +      ) 
 +    ) 
 +  ) 
 +) 
 +</code> 
 + 
 + 
 +===== Seznamy a stromy =====   
 +**Reprezentace seznamů a stromů ve Scheme/Racketu.** 
 +=== Pár === 
 +Základní stavební blok je **pár (pair)**. Drží dvě hodnoty, které lze získat voláním car (první prvek) / cdr (list bez prvního prvku). 
 + 
 +<code scheme> 
 +(cons #\A 65) => '(#\A . 65) 
 + 
 +(define p (cons #\A 65)) 
 +(car p) => #\A 
 +(cdr p) => 65 
 +</code> 
 + 
 +Páry lze do sebe zanořit:  
 +<code scheme> 
 +(cons (cons 1 (cons 2 3)) (cons 'b #f)) 
 +</code> 
 + 
 +=== Seznam === 
 +**Seznam (list)** je sekvence hodnot. Může nabývat libovolné délky a prázdný seznam značíme '() nebo null. 
 +<markdown> 
 +Seznam můžeme vztvořit následujícími způsoby: 
 +  1. Použitím zanořených párů : 
 +  ```scheme 
 +(cons 1 (cons 2 (cons 3 (cons 4 '())))) => '(1 2 3 4) 
 +  ``` 
 +  2. Funkcí **list**, která bere sekvenci výrazů, a vrátí seznam hodnoty vytvořené vyhodnocením všech těchto výrazů:   
 +  ```scheme 
 +(list 1 2 3 4) => '(1 2 3 4) 
 +(list 1 2 (+ 2 1) 4) => '(1 2 3 4) 
 +  ``` 
 + 
 +  3. Funkcí **quote**, která, na rozdíl od list, přijme jediný výraz (typu (fn arg1 arg2 ... argN)) a vrátí seznam jeho komponent bez vyhodnocení: 
 +  ```scheme 
 +(quote (1 2 (+ 2 1) 4)) => '(1 2 (+ 2 1) 4) 
 +  ``` 
 +  protože se používá často, lze zkrátit: 
 +  ```scheme 
 +(quote exp) --> 'exp 
 +  ``` 
 +  4. Funkcí **quasiquote** - kombinace předchozích funkcí, tedy dovolí nám vzhodnotit jen některé výrazy pomocí funcke **unquote**: 
 +  ```scheme 
 +(quasiquote (* 1 (unquote (+ 1 1)) 2)) => '(* 1 2 2)` 
 +  ``` 
 +  5. Spojením seznamů : 
 +  ```scheme 
 +(append '(1) '(2) '(3 4)) => '(1 2 3 4) 
 +  ``` 
 + 
 +Pracovat se seznamy nám dovolují následující funkce: 
 + 
 +**car** vrací první prvek seznamu `(car (list 1 2 3 4)) => 1` 
 + 
 +**cdr** vrací seznam bez prvního prvku `(cdr (list 1 2 3 4)) => '(2 3 4)` 
 + 
 +Další prvky lze získat kompozicí car a cdr `(car (cdr (cdr (list 1 2 3 4)))) => 3` 
 +což lze zkrátit na `(caddr (list 1 2 3 4)) => 3` 
 + 
 + 
 +Prázdnost seznamu lze oveřit použitím **null** 
 +` (null? (list 1 2 3 4)) => #f 
 + (null? '()) => #t` 
 + 
 +=== Strom === 
 + 
 +Stromové struktury můžeme reprezentovat za pomocí vnořených seznamů, například uzel lze definovat jako seznam 
 +`'(data left right)` 
 +který drží data a pravý a levý podstrom.  
 + 
 +Můžeme si zavést přístupové funkce 
 +```scheme 
 +(define get-data car) 
 +(define get-left cadr) 
 +(define get-right caddr) 
 +``` 
 +</markdown> 
 + 
 +{{statnice:bakalar:fuptree.png?300}} 
 + 
 +<markdown> 
 +Tento strom lze reprezentovat následovně, pokud definujeme prázdný strom jako #f: 
 +``` 
 +(define btree 
 +  '(1 
 +    (2 
 +     (4 
 +      (7 #f #f) 
 +      #f) 
 +     (5 #f #f)) 
 +    (3 
 +     (6 
 +      (8 #f #f) 
 +      (9 #f #f)) 
 +     #f))) 
 +``` 
 + 
 +Můžeme definovat funcki **find**, která bude vracet seznam uzlů, které spňují predikát: 
 +``` 
 +(define (find pred tree) 
 +  (if tree 
 +      (let* ([data (get-data tree)] 
 +             [left (find pred (get-left tree))] 
 +             [right (find pred (get-right tree))] 
 +             [both (append left right)]) 
 +        (if (pred data) 
 +            (cons data both) 
 +            both)) 
 +      '())) 
 +``` 
 + 
 +Potom lze např. použít pro extrakci všech hodnot vět ích než 5: `(find (lambda (x) (> x 5)) btree) => '(7 6 8 9)` 
 + 
 +Dalším příkladem stromů jsou výrazy:  
 +`13, '(+ 1 2 3), '(* (opp -2) (+ 1 2))` 
 +</markdown> 
 + 
 +{{statnice:bakalar:fupexprtree.png?300}} 
 + 
 +<markdown> 
 +``` 
 +(eval-expr '(* (opp -2) (+ 1 2))) 
 +=> (eval-expr '(* 2 3)) 
 +=> (eval-expr 6) 
 +=> 6 
 +``` 
 + 
 +Definujeme funkci eval-expr, která vyhodnotí výraz zadaný v seznamu: 
 +``` 
 +(define (eval-expr e) 
 +  (if (number? e) 
 +    e 
 +    (let ([op (car e)] [children (map eval-expr (cdr e))]) 
 +    (cond 
 +    [(eq? op '+) (apply + children)] 
 +    [(eq? op '-) (apply - children)] 
 +    [(eq? op '*) (apply * children)] 
 +    [(eq? op 'opp) (- (car children))])))) 
 +``` 
 + 
 +Funkce **apply** bere funkci a seznam argumentů a "rozbalí" argumenty: 
 +` (apply + '(1 2 3)) => (+ 1 2 3)` 
 +</markdown> 
 +===== Víceřádové funkce =====   
 +**Víceřádové funkce (higher-order functions), příklady, currying a částečně vyhodnocené funkce, levý a pravý fold.**   
 +<markdown> 
 + 
 +Víceřádové funkce jsou funkce, které mohou přijímat jiné funkce jako argumenty nebo vracet funkce jako výstup. 
 + 
 +Příklad v Racketu: 
 +```scheme 
 +(define (apply-twice f x) 
 +  (f (f x)) 
 +) 
 +(apply-twice (lambda (x) (+ x 1)) 5) ; => 7 
 +``` 
 +Tato funkce `apply-twice` přijímá funkci `f` a hodnotu `x`, a aplikuje funkci `f` dvakrát na hodnotu `x`. 
 + 
 +Další příklad který vrací funkci: 
 +```scheme 
 +(define (make-adder x) 
 +  (lambda (y) (+ x y)) 
 +) 
 +(define add5 (make-adder 5)) 
 +(add5 10) ; => 15 
 +``` 
 +Tato funkce `make-adder` vrací funkci, která přičte k hodnotě `y` hodnotu `x`, která byla předána při vytvoření této funkce. 
 + 
 +Často zabudované higher-order funkce zahrnují `map`, `filter` a `foldl`/`foldr`. 
 +</markdown> 
 + 
 +==== Currying ==== 
 +<markdown> 
 + 
 +Currying umožňuje převést funkci na sekvenci funkcí, které přijímají jeden argument, technicky definováno jako $\text{curry}(f(x1, x2, ..., xn)->y) = (x1 -> (x2 -> (... -> (xn -> y) ...)))$, kde f. 
 + 
 +Příklad v Racketu: 
 + 
 +```scheme 
 +(define (add x y z) 
 +  (+ x y z)) 
 + 
 +(define curry-add (curry add))   ; ⬅ jeden identifikátor, ne „=“ 
 + 
 +; postupná aplikace: 
 +(((curry-add 1) 5) 6)   ; => 12 
 + 
 +; můžeš ale přidat víc argumentů naráz: 
 +((curry-add 1 5) 6)     ; => 12 
 +((curry-add 1) 5 6)     ; => 12 
 +(curry-add 1 5 6)       ; => 12 
 +``` 
 +</markdown> 
 +==== Částečně vyhodnocené funkce ==== 
 +<markdown> 
 +Částečně vyhodnocené funkce jsou funkce, které jsou aplikovány na méně argumentů, než kolik jich očekávají. Výsledkem je nová funkce, která očekává zbývající argumenty. 
 + 
 +Příklad v haskellu: 
 +```haskell 
 +add :: Int -> Int -> Int -> Int 
 +add x y z = x + y + z 
 +add5 :: Int -> Int -> Int 
 +add5 = add 5 
 + 
 +add5 10 20 -- => 35 
 +``` 
 +</markdown> 
 +==== Levý a pravý fold ==== 
 +<markdown> 
 +Levý fold (`foldl`) a pravý fold (`foldr`) jsou funkce vyššího řádu, které projdou seznam a postupně kombinují jeho prvky pomocí zadané funkce `f`. 
 +</markdown> 
 + 
 +=== Levý fold (`foldl`) === 
 +<markdown> 
 +`foldl` aplikuje funkci zleva doprava a je tail-rekurzivní, takže v přísně vyhodnocovaných jazycích (např. Racket) běží s konstantní hloubkou zásobníku. 
 + 
 +**Parametry** 
 + 
 +* `f` – binární funkce `(acc elem) -> nový-acc` 
 +* `acc` – počáteční akumulátor 
 +* `lst` – seznam 
 + 
 +**Průběh** 
 + 
 +1. Startuje s akumulátorem `acc`. 
 +2. Pro každý prvek `x` ze seznamu volá `(f acc x)` a výsledek uloží do `acc`. 
 +3. Po zpracování posledního prvku vrátí finální `acc`. 
 + 
 +**Příklad (Racket)**   
 +```scheme 
 +#lang racket 
 +(require racket/list) 
 + 
 +(define lst '(1 2 3 4)) 
 +(foldl + 0 lst) ; => 10 
 +``` 
 + 
 +Syntaktický strom levého foldu: 
 +``` 
 +(foldl f acc (list a b c d)) 
 +=> 
 +(foldl f (f acc a) (list b c d)) 
 +(foldl f (f (f acc a) b) (list c d)) 
 +(foldl f (f (f (f acc a) b) c) (list d)) 
 +(foldl f (f (f (f (f acc a) b) c) d) '()) 
 +``` 
 +</markdown> 
 +=== Pravý fold (foldr) === 
 +<markdown> 
 +Pravý fold (foldr) zpracovává seznam zprava doleva. Není tail-rekurzivní, takže na dlouhých seznamech může v přísně vyhodnocovaném prostředí přetéct zásobník. 
 + 
 +Kroky: 
 +1. Pokud je seznam prázdný, vrátí `acc`. 
 +2. Vezme první prvek `a` a zavolá `(f a (foldr f acc (rest lst)))`. 
 +   Tím vznikne pravě-asociovaný řetězec volání `f`. 
 + 
 +Příklad v Racketu: 
 +```scheme 
 +(require racket/list) 
 +(define lst '(1 2 3 4)) 
 +(foldr + 0 lst) ; => 10 
 +``` 
 + 
 +Syntaktický strom právého foldu: 
 +``` 
 +(foldr f acc (list a b c d)) 
 +=> f a (foldr f acc (list b c d)) 
 +=> f a (f b (foldr f acc (list c d))) 
 +=> f a (f b (f c (foldr f acc (list d)))) 
 +=> f a (f b (f c (f d acc))) 
 +``` 
 +</markdown> 
 + 
 +===== Funkční uzávěry (Lambda funkce) =====   
 +**Funkční (neboli lexikální) uzávěry, příklady.** 
 +<markdown> 
 +Volná Proměná (free variables) - proměnná která je použitá uvnitř funkce, ale není její parametr ani není definovaná uvnitř funkce. 
 + 
 +Funkční uzávěr (closure) - prostředí ve kterém byla funkce vytvořena. Obsahuje všechny definice volných proměnných, které jsou použity v těle funkce. Uzávěr tedy "uzavírá" proměnné, které jsou dostupné v době jejího vytvoření. 
 + 
 +Například funkce v racketu: 
 +```scheme 
 +(define (make-adder x) 
 +  (lambda (y) (+ x y)) 
 +) 
 + 
 +(define add5 (make-adder 5)) 
 + 
 +(add5 10) ; => 15 
 +``` 
 + 
 +V tomto případě `make-adder` vytváří closure, který obsahuje v případě `add5` hodnotu `x = 5`. Když zavoláme `add5`, použije tuto hodnotu `x` a přičte ji k `y`. 
 + 
 + 
 +</markdown>   
 +===== Lambda kalkulus ===== 
 +**Lambda kalkulus, alfa‑konverze, beta‑redukce, evaluační strategie (normal a applicative), normální forma, Church‑Rosserova věta, Y‑kombinátor.** 
 +Lambda kalkulus je formální systém pro vyjadřování výpočtů pomocí funkcí. Je základem pro mnoho funkcionálních programovacích jazyků, včetně Haskellu a Racketu. 
 + 
 +<markdown> 
 +Programy v lambda kalkulu jsou tvořeny funkcemi definovanými pomocí *lambda výrazů*. Lambda výraz má tvar 
 + 
 +``` 
 +term ::= var | func | app 
 +func ::= (λ var . term) 
 +app  ::= term term 
 +``` 
 + 
 +Každý lambda výraz může být buď proměnná (*var*), funkce (*func*) nebo aplikace (*app*) funkce na argumenty. 
 + 
 + 
 + 
 +### Alfa‑konverze 
 + 
 +Alfa‑konverze je přejmenování proměnných, aby se zabránilo kolizím jmen, např. 
 + 
 +$(\lambda x.,x) ;\rightsquigarrow; (\lambda y.,y)$ 
 + 
 + 
 + 
 +### Beta‑redukce 
 + 
 +Beta‑redukce aplikuje funkci na argument. Formálně 
 + 
 +$\bigl(\lambda x.,t\bigr);v ;\rightarrow\_{\beta}; t\[,x := v,]$. 
 + 
 +Příklad: 
 + 
 +$(\lambda x.,x)(\lambda y.,y) 
 +;\rightarrow\_{\beta}; 
 +(\lambda y.,y)(\lambda y.,y) 
 +;\rightarrow\_{\beta}; 
 +(\lambda y.,y).$ 
 + 
 + 
 +### Normální forma a redex 
 + 
 +* **Normální forma** – výraz, v němž už neexistuje žádný $\beta$‑redex. 
 +* **Redex** – podvýraz tvaru $(\lambda x.,t),v$. 
 + 
 +Velmi často se na vizualizaci lambda kalkulu používají diagramy, které ukazují strukturu výrazů a jejich redukce. Například výraz $(\lambda x.,x)(\lambda y.,y)$ lze zobrazit jako strom: 
 +</markdown> 
 + 
 +<tikzjax> 
 +\usetikzlibrary{arrows.meta} 
 + 
 +\begin{document} 
 +\begin{tikzpicture}\[ 
 +every node/.style={draw, circle, inner sep=2pt, font=\small}, 
 +level distance=15mm, 
 +sibling distance=28mm 
 +] 
 +\node {@} 
 +child { node {$\lambda x$} 
 +child { node {$x$} } 
 +} 
 +child { node {$\lambda y$} 
 +child { node {$y$} } 
 +}; 
 +\end{tikzpicture} 
 +\end{document} </tikzjax> 
 + 
 +==== Evaluační strategie ====  
 +<markdown> 
 +Evaluační strategie určuje, jak se vyhodnocují lambda výrazy. 
 + 
 +1. **Normal order** – redukuje vždy nejlevější vnější redex; zaručí normální formu, existuje‑li. 
 +2. **Applicative order** – nejprve redukuje nejvnitřnější redexy; v případě nekonečné rekurze může divergovat, i když normal order by skončil. 
 + 
 +Příklad rozlišení vnitřního a vnějšího redexu: 
 + 
 +$(\lambda y.,y)\bigl((\lambda z.,z z),x\bigr),\bigl((\lambda z.,(\lambda a.,a),z),(\lambda y.,(\lambda z.,z),x)\bigr)$ </markdown> 
 +{{statnice\:redexes.d0o4rzl0.png}} 
 + 
 +==== Church‑Rosserova věta ==== 
 + 
 +1. Má‑li výraz normální formu, je **jedinečná**. 
 +2. Normal‑order evaluace vždy skončí v normální formě, pokud existuje. 
 + 
 +=== Y‑kombinátor === 
 +`Y` je **fixpoint combinator**, který umožní definovat rekurzi bez pojmenování. 
 + 
 +$$ 
 +Y \;\triangleq\; \lambda f.,(\lambda x.,f,(x,x)),(\lambda x.,f,(x,x)) 
 +$$ 
 + 
 +* **Fixpoint vlastnost**: $Y,f ;\rightarrow\_{\beta}; f,(Y,f)$. 
 +* **Intuice redukce** 
 + 
 +$$ 
 +Y,f 
 +\;\rightarrow_{\beta}\; (\lambda x.,f,(x,x)),(\lambda x.,f,(x,x)) 
 +\;\rightarrow_{\beta}\; f\Bigl((\lambda x.,f,(x,x)),(\lambda x.,f,(x,x))\Bigr) 
 +\;\rightarrow_{\beta}\; f,(Y,f) 
 +$$ 
 + 
 +* **Faktoriál (schematicky, Racket)** 
 + 
 +```scheme 
 +(define FACT 
 +  (Y (λfact 
 +       (λn (if (= n 0) 1 (* n (fact (- n 1)))))))) 
 +        
 +``` 
 + 
 +* **Kde funguje** 
 + 
 +  * *Lazy/normal‑order* (Haskell) – `Y` přímo funguje. 
 +  * *Strict/applicative* (Racket, JS) – je potřeba `Z`‑kombinátor (lazy fixpoint). 
 + 
 +Stručně: **`Y` přidá rekurzi** tím, že každé funkci vrátí její vlastní výsledek jako argument. 
 + 
 + 
 +===== ADT v Haskellu =====   
 +<markdown> 
 +**Algebraické datove typy (ADT) v Haskellu, příklad rekurzivního ADT.**   
 +**Algebraické datové typy (ADT)** v Haskellu slouží pro definici vlastních typů. Umožňují vytvářet nové datové struktury kombinováním:: 
 +  1. **součtových typů** (sum types, více variant) 
 +  2. **součinových typů** (product types, více polí v jedné variantě) 
 + 
 +Definují se pomocí **data**: 
 +` data Answer = Yes | No | Unknown ` 
 + 
 +Answer = typový konstruktor 
 +Yes, No, Unknown = datové konstruktory 
 +Konstruktory začínají velkým písmenem. 
 + 
 +``` 
 +answers :: [Answer] 
 +answers = [Yes,No,Unknown] 
 + 
 +flip :: Answer -> Answer 
 +flip Yes = No 
 +flip No = Yes 
 +flip Unknown = Unknown 
 +``` 
 +</markdown> 
 +=== Parametrické ADT === 
 +<markdown> 
 +`data Shape = Circle Float | Rect Float Float` 
 +**Circle** a **Rect** jsou funkce které konstruují hodnoty typu **Shape** 
 + 
 +``` 
 +square :: Float -> Shape 
 +square n = Rect n n 
 +``` 
 + 
 +Jeden z nejčastějších datových typů je:  
 +`data Maybe a = Nothing | Just a` 
 +který potom zaručuje bezpečné operace:  
 +``` 
 +safediv :: Int -> Int -> Maybe Int 
 +safediv _ 0 = Nothing 
 +safediv m n = Just (m `div` n) 
 +``` 
 + 
 +</markdown> 
 +=== Records  === 
 +<markdown> 
 +Deklarace závislé čistě na pozici bývají nepraktické, proto lze pole pojmenovat: 
 +``` 
 +data Person = Person { firstName :: String, 
 +lastName :: String, 
 +age :: Int, 
 +phone :: String, 
 +address :: String } 
 +``` 
 + 
 +</markdown> 
 +=== Rekurzivní ADT === 
 +<markdown> 
 +Rekurzivní ADT odkazují na sebe sama — umožňují reprezentovat seznamy, stromy, výrazy apod. 
 + 
 +`data List a = Nil | Cons a (List a) deriving Show` 
 +Nil = prázdný seznam 
 +Cons = prvek a zbytek seznamu 
 +Příklad hodnoty: `Cons 1 (Cons 2 (Cons 3 Nil)) :: Num a => List a` 
 + 
 +Dalším příkladem je vyhodnocování výrazů: 
 +``` 
 +data Expr a = Val a 
 +            | Add (Expr a) (Expr a) 
 +            | Mul (Expr a) (Expr a) 
 +``` 
 + 
 + 
 + 
 +</markdown> 
 +===== Typové třídy =====   
 +**Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.**   
 + 
 +{{statnice:bakalar:haskell-typeclasses.B75NDeb3.png?600}} 
 + 
 +===== Functor, Applicative, Monad =====   
 +**Typové třídy Functor, Applicative functor, Monad a jejich použití.**   
 + 
 +=== Funktor === 
 + 
 +Funktor je typ , který implementuje funkci $\texttt{fmap}$, tím jsou všechny funktory "mapovatelné". 
 + 
 +<code haskell> 
 +class Functor f where 
 +  fmap :: (a -> b) -> f a -> f b 
 +</code> 
 + 
 +<code haskell> 
 +data Tree a = Tree a [Tree a] deriving Show 
 + 
 +instance Functor Tree where 
 +  fmap f (Tree x []) = Tree (f x) [] 
 +  fmap f (Tree x ts) = Tree (f x) 
 +                            (map (fmap f) ts) 
 +</code> 
 + 
 +Identita: 
 +  fmap id == id 
 + 
 +Kompozice: 
 +  fmap (f . g) == fmap f . fmap g 
 + 
 +=== Applicative funktor === 
 + 
 +Funktor, který má navíc definovanou operaci $\texttt{<*>}$ (apply) a funkci pure. 
 + 
 +<code haskell> 
 +class (Functor f) => Applicative f where   
 +    pure :: a -> f a   
 +    (<*>) :: f (a -> b) -> f a -> f b   
 +</code> 
 + 
 +<code haskell> 
 +instance Applicative Maybe where 
 +    pure = Just 
 +    Nothing <*> _ = Nothing 
 +    (Just f) <*> something = fmap f something 
 +</code> 
 + 
 +=== Monáda === 
 + 
 +Applicative funktor, který má navíc ještě bind. Jedná se o abstrakci nad výpočtem s kontextem (podle typu). 
 + 
 +Bind ''%%(>>=)%%'' funguje jako zřetězení operací. Operace, která přijímá zabalenou hodnotu s typem a, rozbalí ji, provede nad ní výpočet a vrátí jí zabalenou s typem b. 
 + 
 +<code haskell> 
 +class Applicative m => Monad m where 
 +  (>>=) :: m a -> (a -> m b) -> m b 
 +  return :: a -> m a 
 +</code> 
 + 
 +return je to stejné jako pure v applicative.

Trace: • b4b36fup • b0b01ma2

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b36fup (generated for current page)