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:13] – 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 12: Line 14:
 ===== Čisté funkce =====   ===== Čisté funkce =====  
 **Čisté funkce (pure functions), jejich výhody a nevýhody.**   **Čisté funkce (pure functions), jejich výhody a nevýhody.**  
 +Čistá funkce je taková, která 
 +(1) vrací vždy stejný výsledek pro stejné hodnoty argumentů a 
 +(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.
 +==== Výhody čistých funkcí ====
 +<markdown>
 +- **Determinismus**: Pro stejné vstupy vždy vrací stejné výstupy, což usnadňuje testování a ladění.
 +- **Snadná kompozice**: Čisté funkce lze snadno kombinovat a vytvářet složitější funkce.
 +- **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 =====   ===== Rekurze =====  
 **Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion).**   **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 =====   ===== Seznamy a stromy =====  
-**Reprezentace seznamů a stromů ve Scheme/Racketu.**  +**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 =====  
 **Víceřádové funkce (higher-order functions), příklady, currying a částečně vyhodnocené funkce, levý a pravý fold.**   **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.
  
-===== Funkční uzávěry =====   +Příklad v Racketu: 
-**Funkční (neboli lexikální) uzávěry, příklady.**  +```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.
  
-===== Lambda kalkulus =====   +Často zabudované higher-order funkce zahrnují `map`, `filter` a `foldl`/`foldr`. 
-**Lambda kalkulus, alfa-konverze, beta-redukce, evaluační strategie (normal a applicative), normální forma, Church-Rosserova věta, Y-combinator.**  +</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 =====   ===== ADT v Haskellu =====  
 +<markdown>
 **Algebraické datove typy (ADT) v Haskellu, příklad rekurzivního ADT.**   **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 =====  
 **Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.**   **Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.**  
  
 +{{statnice:bakalar:haskell-typeclasses.B75NDeb3.png?600}}
  
 ===== Functor, Applicative, Monad =====   ===== Functor, Applicative, Monad =====  
 **Typové třídy Functor, Applicative functor, Monad a jejich použití.**   **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 • b4b33alg • b4b01num

Navigation

Playground

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