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 [2026/06/06 14:57] (current) – [Church‑Rosserova věta] knedl1k
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 ===
 +`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

Navigation

Playground

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