Funkcionální jazyky a jejich vlastnosti. Lambda kalkulus, iterativní konstrukty a rekurze.

1. Čisté funkce (pure functions), jejich výhody a nevýhody.
2. Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion).
3. Reprezentace seznamů a stromů ve Scheme/Racketu.
4. Víceřádové funkce (higher-order functions), příklady, currying a částečně vyhodnocené funkce, levý a pravý fold.
5. Funkční (neboli lexikální) uzávěry, příklady.
6. Lambda kalkulus, alfa-konverze, beta-redukce, evaluační strategie (normal a applicative), normální forma, Church-Rosserova věta, Y-combinator.
7. Algebraické datove typy (ADT) v Haskellu, příklad rekurzivního ADT.
8. Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.
9. Typové třídy Functor, Applicative functor, Monad a jejich použití.

Č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.

• 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.

• 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.

Rekurzivní funkce, typy rekurze, koncová rekurze (tail recursion).

Rekurzivní funkce je funkce která volá sama sebe.

(define (fact n)
  (cond ((= 0 n) 1)
    (#t (* n (fact (- n 1))))
  )
)

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):

(define (sum list [acc 0])
  (if (empty? list) 
    acc
    (sum (cdr list) (+ acc (car list)))
  )
)

Tree rekurze (sečtení stromu):

(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))
      )
    )
  )
)

Reprezentace seznamů a stromů ve Scheme/Racketu.

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).

(cons #\A 65) => '(#\A . 65)
 
(define p (cons #\A 65))
(car p) => #\A
(cdr p) => 65

Páry lze do sebe zanořit:

(cons (cons 1 (cons 2 3)) (cons 'b #f))

Seznam (list) je sekvence hodnot. Může nabývat libovolné délky a prázdný seznam značíme '() nebo null.

Seznam můžeme vztvořit následujícími způsoby:

1. Použitím zanořených párů :

   (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ů:

   (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í:

   (quote (1 2 (+ 2 1) 4)) => '(1 2 (+ 2 1) 4)

   protože se používá často, lze zkrátit:

   (quote exp) --> 'exp

4. Funkcí quasiquote - kombinace předchozích funkcí, tedy dovolí nám vzhodnotit jen některé výrazy pomocí funcke unquote:

   (quasiquote (* 1 (unquote (+ 1 1)) 2)) => '(* 1 2 2)`

5. Spojením seznamů :

   (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

(define get-data car)
(define get-left cadr)
(define get-right caddr)

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))

(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)

Víceřádové funkce (higher-order functions), příklady, currying a částečně vyhodnocené funkce, levý a pravý fold.

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:

(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:

(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.

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:

(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

Čá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:

add :: Int -> Int -> Int -> Int
add x y z = x + y + z
add5 :: Int -> Int -> Int
add5 = add 5
 
add5 10 20 -- => 35

Levý fold (foldl) a pravý fold (foldr) jsou funkce vyššího řádu, které projdou seznam a postupně kombinují jeho prvky pomocí zadané funkce f.

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)

#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) '())

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:

(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)))

Funkční (neboli lexikální) uzávěry, příklady.

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:

(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.

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.

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:

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)$

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)

(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.

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

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)

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 }

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)

Typové třídy (type classes) v Haskellu, polymorfismy v Haskellu.

Typové třídy Functor, Applicative functor, Monad a jejich použití.

Funktor je typ , který implementuje funkci $\texttt{fmap}$, tím jsou všechny funktory “mapovatelné”.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

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)

Identita:

fmap id == id

Kompozice:

fmap (f . g) == fmap f . fmap g

Funktor, který má navíc definovanou operaci $\texttt{<*>}$ (apply) a funkci pure.

class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b  

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

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.

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a

return je to stejné jako pure v applicative.