Funkcionální programování

Note	Funkcionální programovací paradigma (princip výpočtu, redukční krok, redukční strategie a jejich vlastnosti, příklady). Funkce vyšších řádů a jejich využití. Lambda funkce. Schopnost elementárního programování v Haskellu. IB015

Funkcionální programování je příkladem deklarativního programovacího paradigmatu. Klade důraz na to, jak má vypadat výsledek, ne nutně, jak se k němu dobrat krok za krokem.

Funkce

Předpis jak z nějakého vstupu udělat výstup. Transformace musí být jednoznačná.

Typ funkce (typová signatura funkce)

Udává, s jakými objekty funkce pracuje a jaký má tvar její výsledek.

Skládání funkcí

$(f \circ g) (n) = g (f (n))$ . Čteme ,, $f$ po $g$ ''.

Funkce vyšších řádů

Alespoň jeden argument a nebo výsledek je funkce. Například:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter f (x:xs)
    | f x = x : filter f xs
    | otherwise = filter f xs

Částečná aplikace

Všechny funkce lze považovat za unární funkce, které vrací další funkce. Částečná aplikace je dosazení prvního argumentu za vzniku nové funkce, která má o parametr méně.

Výpočet

Program jsou definice funkcí a výraz, jehož výsledek nás zajímá.
Výpočet je zjednodušování tohoto výrazu.
Výsledek je nezjednodušitelný tvar tohoto výrazu.

Mějme například následující funkce:

square x = x * x
pyth a b = square a + square b

a výraz

pyth 3 4

Výpočet vypadá takto:

pyth 3 4 $⇝$ square 3 + square 4 $⇝$ 3 * 3 + square 4 $⇝$ 3 * 3 + 4 * 4 $⇝$ 9 + 4 * 4 $⇝$ 9 + 16 $⇝$ 25

Redukční strategie

Redukční krok je úprava výrazu, kdy je vybraný podvýraz nahrazen svou definicí. Podvýraz může být jak volání funkce, tak aritmetická/logická/jiná operace. (V Haskellu to jsou stejně taky funkce.)

Redukční strategie je pak způsob výběru podvýrazu, který má být v daném kroku zjednodušen.

Striktní redukční strategie: Jde ,,zevnitř''. Nejdřív upraví argumenty a až potom aplikuje funkci.

square (3 + 5) $⇝$ square 8 $⇝$ 8 * 8 $⇝$ 64
Normální redukční strategie: Jde ,,zvenku''. Nejdřív aplikuje funkci a argumenty upravuje, až jsou potřeba.

square (3 + 5) $⇝$ (3 + 5) * (3 + 5) $⇝$ 8 * (3 + 5) $⇝$ 8 * 8 $⇝$ 64
Líná redukční strategie: Normální redukční strategie, ale pamatuje si výsledky podvýrazů a žádný nevyhodnocuje víc než jednou.

square (3 + 5) $⇝$ (3 + 5) * (3 + 5) $⇝$ 8 * 8 $⇝$ 64
Věta o perpetualitě: Jestliže se výraz zacyklí s nějakou redukční strategií, určitě se zacyklí se striktní redukční strategií.
Věta o normalizaci: Pokud se výraz nezacyklí s nějakou redukční strategií, určitě se nezacyklí ani s normální redukční strategií.
Churchova-Rosserova věta: Pokud výpočet skončí, výsledek nezáleží na zvolené redukční strategii.

Lambda funkce

Nepojmenovaná funkce, která je defininována přímo v místě použití.

Lambda abstrakce je proces tvorby lambda funkcí. Mějme výraz $M \equiv x + 42$ . $M$ je tělo funkce, z něhož lambda funkci vyrobíme takto: $λ x . M \equiv λ x . (x + 42)$ .

Například v Haskellu:

map (\x -> x + 42) [1, 2, 3, 4, 5]

je ekvivaletní s

map f [1, 2, 3, 4, 5] where
    f x = x + 42

a vrátí

[43, 44, 45, 46, 47]

Haskell

Funkcionální programovací jazyk. Používá normální redukční strategii, ale zastaví už v weak head normal form (WHNF) — formě která sice zjednodušit jde, ale nejvnějšnější výraz je konstruktor nebo lambda.

Základní datové typy

Int, Float, Fractional, Char, String, Bool.

Deklarace a definice funkce

one_or_two :: Integer -> Bool
one_or_two 1 = True
one_or_two 2 = True
one_or_two _ = False

Typový kontext

Funkce a typy mohou chtít pracovat s libovolnými typy, které splňují nějaké podmínky.

(==) :: Eq a => a -> a -> Bool
(==) l r = undefined

Referenční transparence

Haskell je referenčně transparentní — výsledek výrazu nezávisí na kontextu, ve kterém se vyhodnocuje. Může mít veldejší efekt, ale ten nesmí ovlivnit výsledek.