The wiki page is under active construction, expect bugs.

Differences

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

Link to this comparison view

Next revision		Previous revision
statnice:bakalar:b4b36fup [2025/05/25 11:04] – created mistrjirkastatnice:bakalar:b4b36fup [2025/05/27 19:21] (current) – [Seznamy a stromy] prokop
Line 1: Line 1:
-======= Funkcionální jazyky a jejich vlastnosti. Lambda kalkulus, iterativní konstrukty a rekurze. ======+[[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. ======
   - Č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).   - Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion).
Line 9: Line 11:
   - Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.   - Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.
   - Typové třídy Functor, Applicative functor, Monad a jejich použití.   - Typové třídy Functor, Applicative functor, Monad a jejich použití.
 +
 +===== Čisté funkce =====  
 +**Č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 =====  
 +**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 === <markdown>
 +`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.
 +>
 +> </markdown>
 +
 +
 +===== 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:

Navigation

Playground

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