statnice:bakalar:b4b36fup

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
[[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]]

====== Funkcionální jazyky a jejich vlastnosti. Lambda kalkulus, iterativní konstrukty a rekurze. ======
  - Čisté funkce (pure functions), jejich výhody a nevýhody.
  - Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion).
  - Reprezentace seznamů a stromů ve Scheme/Racketu.
  - Víceřádové funkce (higher-order functions), příklady, currying a částečně vyhodnocené funkce, levý a pravý fold.
  - Funkční (neboli lexikální) uzávěry, příklady.
  - Lambda kalkulus, alfa-konverze, beta-redukce, evaluační strategie (normal a applicative), normální forma, Church-Rosserova věta, Y-combinator.
  - Algebraické datove typy (ADT) v Haskellu, příklad rekurzivního ADT.
  - Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.
  - 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: • b0b01lag • b0b01ma1 • b4b32pks • b4b01dma • b4b36pdv • b0b01lgr • b4b17eam • b0b33opt • b0b01ma2 • b4b35psr
Search

Navigation

Print/export

Tools

QR Code
