Obsah

AP6, IN6 Rekurze

(rekurzivní definice funkcí, funkce vyššího řádu, částečná aplikace, curryifikace, definice funkcí rekurzivně a pomocí kombinátorů, definice vyšších funkcí bez použití formálních parametrů)

Definice funkcí

To, co dává funkcionálním jazykům vyjadřovací sílu, je možnost definovat nové funkce a neomezovat se na již vestavěné. Funkce ve funkcionálních jazycích definujeme předpisy, ve kterých kromě jména funkce zapisujeme nalevo také její parametry, což budou v nejjednodušším případě jména proměnných.

Třetí mocnina

cube x = x * x * x

Maximální hodnota ze tří zadaných

max3 a b c = max a (max b c)

Nové operátory se definují stejným způsobem jako funkce.

Definice operátoru

(.-.) u v = if u > v 
               then u - v 
               else 0

Rekurzivní definice funkce

Podstatným důvodem, proč definice nových funkcí zvyšuje naši vyjadřovací sílu, je fakt, že definice mohou být rekurzivní.

Faktoriál

fact n = if n == 0 
            then 1 
            else n * fact (n - 1)

N tá mocnina

a^n = if n == 0 
         then 1 
         else a * a^(n - 1)

Rozlišujeme dva druhy rekurze:

Příklad přímé rekurze

map f [] = [] 
map f (x:xs) = f x : map f xs

Příklad nepřímé rekurze

even n = if n == 0 
            then True 
            else odd (n - 1) 
odd n = if n == 0 
           then False 
           else even (n - 1)

Funkce vyšších řádů

Některé programovací jazyky pohlížejí na funkce jen jako na jednoparametrické (unární) funkce. Aplikace funkce na n argumentů:

f x_{1} x_{2} ... x_{n-1} x_{n}

je ve skutečnosti jednoduchou aplikací funkce (( ... ((f x_{1}) x_{2}) ... ) x_{n-1}) na jediný argument x_{n} tedy :

(( ... ((f x_{1}) x_{2}) ... ) x_{n-1}) x_{n}

Pomyslný operátor „aplikace“ tedy vlastně sdružuje zleva.

Příklad

Ve výrazu (+) 3 4 se operátor (+) nejdříve aplikuje na svůj (jediný) argument 3, výsledkem této aplikace je funkce ( (+) 3), která je-li aplikována na argument, přičte k němu číslo 3, výsledný součet bude výsledkem této druhé akce – ( (+) 3) 4.

  • Funkce vyšších řádů jsou v podstatě funkce, jejichž argument nebo výsledek může být zase funkce.

Částečná aplikace

Částečná aplikace se říká aplikaci nějaké funkce na „menší počet argumentů než je obvyklé“. Přesněji je to aplikace, jejímž výsledkem je funkce. Například v následující definici je operátor částečně aplikován na argument 3. 

add3 = (+) 3

Curryifikace

Jeden ze způsobů, jak zachovat víceparametrické funkce, je spojit jejich argumenty do n-tic. Tím se však ztrácí možnost takovéto funkce částečně aplikovat. Dají se však převést na funkce vyšších řádů pomocí procesu zvaného curryifikace.
Uvažme dvě funkce add a add', které realizují sčítání celých čísel, ale mají různý typ. 

add :: Int -> Int -> Int 
add x y = x + y

Funkce add je vyšší funkce, může být aplikována i na jediný argument, tato aplikace vrátí funkci (například add 3 je funkce, která k zadaném argumentu přičítá číslo 3). 

add' :: (Int,Int) -> Int 
add' (x,y) = x + y

Funkce add' požaduje jako argument uspořádanou dvojici a jako výsledek vrací součet prvků dvojice.

Výhoda funkce add oproti funkci add' spočívá právě v tom, že ji můžeme částečně aplikovat na jediný argument, a získat tak zase funkci. Kdybychom chtěli totéž provést s funkcí add' potřebovali bychom k tomu zavedené pomocné funkce, funkce : 

add'' x y = add' (x,y)

Obecně z každé funkce f', která má jako argument n-tici, je možné vytvořit vyšší funkci, kterou lze postupně aplikovat na n argumentů odpovídajícím složkám n-tice. Tomuto převodu nižších funkcí na vyšší se říká curryifikace.1)

Mějme dvě funkce, f a g, obě se dvěma parametry, definované pomocí stejného výrazu c. 

f x y    = c 
g (x,y)  = c

Přechod od funkce g k funkci f je v jazyce Haskell pro binární funkce řešen pomocí funkce curry. 

curry :: ((a,b) -> c) -> a -> b -> c  
curry g x y  = g (x,y)

Funkce curry vezme funkci g, která je zvyklá brát jako svůj parametr dvojici.
Dále vezme dva parametry x, y a funkci g je předá, zabalené do oné dvojice.
Funkce g je tedy nižší; vyžaduje dvojici parametrů, nelze ji aplikovat jen na x.
Funkce curry g je naopak vyšší: můžeme ji částečně aplikovat na pouhé x a vytvořit
tak funkci, která očekává parametr y. Něco takového s funkcí g bez curryfikace
neumíme.

A přechod od funkce f k funkci g je v jazyce Haskell pro binární funkce řešen pomocí funkce uncurry. 

uncurry :: (a -> b -> c) -> (a,b) -> c 
uncurry f (x,y)  = f x y

Tedy f = curry g; g = uncurry f.

Definice funkcí rekurzivně a pomocí kombinátorů

reverse = foldl (flip (:)) []

obsahuje funkci (kombinátor) foldl, která sama ve své definici rekurzi obsahuje, a funkci (kombinátor) flip, která rekurzivní není.

Funkce foldr

foldr :: (b → a → a) → a → [b] → a 
foldr _ a []     = a 
foldr op a (x:s) = x `op` foldr op a s

`op` je infixový zápis aplikace binární funkce.
a `op` b je totez jako op a b

and = foldr (&&) True 

or  = foldr (||) False 
concat = foldr (++) [] 
compose = foldr (.) id

  • Nejčastější kombinátory jsou funkce (.), flip, const, id a funkce, která nemá přímo v jazyce Haskell zavedený název, říkejme jí např. dist

dist f g x = f x (g x)

  • Definice funkce pomocí kombinátorů je často kratší a „elegantnější“.

Definice vyšších funkcí bez použití formálních parametrů

Vyšší funkce lze často za pomoci kombinátorů definovat tak, že lze vynechat formální parametry – zápis je tak jednodušší, kratší a přehlednější. Například funkci zip lze vyjádřit pomocí funkce zipWith. Funkce zip je zde definována předpisem, který říká, že „zip se chová“ na argumentech s a t stejně jako funkce zipWith (,) na argumentech s a t. 2) 

zip s t = zipWith (,) s t

Funkce zip rovna tedy funkci zipWith (,) a původní definici můžeme zkrátit 

zip = zipWith (,)

Tomuto zkrácení se říká eta-redukce (čti eta redukce), vyplývá z tzv. principu extensionality, který říká: Jestliže platí f x = g x pro všechna x ze sjednocení definičních oborů funkcí f a g, pak f = g. (Laicky, když popisujeme funkci pomocí jiné funkce a mají stejné formální parametry ve stejném pořadí, tak je nemusíme uvádět.) 3)

Co lze ještě k otázce zmínit

Funkce lze definovat také pomocí vzorů. Vzor popisuje množinu argumentů, které tomuto vzoru vyhovují. Definice funkce se pak rozpadá na více větví, klausulí. Při výpočtu se pak z definice použije ta větev, jejíž vzory vyhovují skutečným argumentům. Vzor je obecněji výraz, jehož žádný podvýraz nelze redukovat – skládá se pouze z proměnných a tzv. konstruktorů.4)

Rekurzivní definici funkce fact lze pomocí vzorů zapsat

fact 0 = 1 
fact n = n * fact (n - 1)

Co byste ještě měli znát?

Předměty

Použitá literatura

Kam dál

Vhodné doplnění studia může být vyzkoušení příkladů ze cvičení prakticky v interpretu haskelu Hugs.
Nebo třeba trošku populárněji psaný seriál o funkcionálním programování na Programujte.com.
O tomto tématu také píše BONUS v jeho příručce Haskellu.

Vypracoval

Winsik - ICQ: 215787520 mail: winsik.cz(zavinac)gmail.com
Jitunka - ICQ: 218703195 (jen doplňující informace a poslední dvě podčásti otázky)

Otázku si přečetl pan RNDr. Libor Škarvada a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen rámcová, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

1)
miniskripta, kapitola 6, strana 29
2)
Miniskripta – zápisky z přednášek, kapitola 6, strana 26
3)
Miniskripta - zápisky z přednášek, kapitola 6, strana 26
4)
miniskripta, kapitola 2, strana 9