====== 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.
cube x = x * x * x
max3 a b c = max a (max b c)
Nové operátory se definují stejným způsobem jako funkce.
(.-.) 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í.
fact n = if n == 0
then 1
else n * fact (n - 1)
a^n = if n == 0
then 1
else a * a^(n - 1)
Rozlišujeme dva druhy rekurze:
* **Přímá rekurze** nastává, pokud funkce volá přímo sama sebe.
map f [] = []
map f (x:xs) = f x : map f xs
* **Nepřímá (vzájemná) rekurze** je situace, kdy dvě funkce (nebo i více funkcí) volají vzájemně jedna druhou.
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.
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.((miniskripta, kapitola 6, strana 29))
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ů =====
* Funkce lze definovat rekurzivně (viz příklady v sekci //Rekurzivní definice funkce//) tak, že funkce volá sama sebe.
* Funkce lze ale definovat pomocí tzv. **kombinátorů**, tedy pomocí jiných funkcí, které buď samy v sobě rekurzi obsahují či ne. Například definice funkce **reverse**
reverse = foldl (flip (:)) []
obsahuje funkci (kombinátor) **foldl**, která sama ve své definici rekurzi obsahuje, a funkci (kombinátor) **flip**, která rekurzivní není.
* Spoustu funkcí, které pracují se seznamy, lze vyjádřit pomocí tzv. **akumulačních seznamových funkcí foldr a foldl** (které jsou také kombinátory).
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**. ((Miniskripta -- zápisky z přednášek, kapitola 6, strana 26))
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.) ((Miniskripta - zápisky z přednášek, kapitola 6, strana 26))
===== 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ů.((miniskripta, kapitola 2, strana 9))
fact 0 = 1
fact n = n * fact (n - 1)
====== Co byste ještě měli znát? =====
* Měli byste vědět, jakým způsobem lze rekurzi "odstranit", tedy jak můžete například program počítající faktoriál napsat bez použití rekurze. Je dobré tento program pak přímo zapsat v nějakém (imperativním) jazyce na tabuli.
====== Předměty ======
* [[https://is.muni.cz/auth/predmety/predmet.pl?kod=IB015;fakulta=1433;obdobi=|FI:IB015]] Úvod do funkcionálního programování (jaro), [[https://is.muni.cz/auth/lide/?searchid=%C5%A1karvada&Hledat=Hledat&zpet=.%2F&zpet_text=Zp%C4%9Bt+na+hled%C3%A1n%C3%AD+osob| RNDr. Libor Škarvada]]
====== Použitá literatura ======
* RNDr. Libor Škarvada, [[http://www.fi.muni.cz/%7Elibor/vyuka/IB015/cviceni/index.html|Cvičení k předmětu]]
* RNDr. Libor Škarvada, [[http://www.fi.muni.cz/%7Elibor/vyuka/IB015/zapisky.pdf|Miniskripta - zápisky z přednášek]]
====== Kam dál ======
Vhodné doplnění studia může být vyzkoušení příkladů ze cvičení prakticky v interpretu **haskelu** [[http://www.haskell.org/hugs/|Hugs]].
Nebo třeba trošku populárněji psaný seriál o funkcionálním programování na [[http://programujte.com/index.php?rubrika=26-programovani&sekce=165-funkcionalni-programovani&kategorie=166-serial-funkc-progr-|Programujte.com]].
O tomto tématu také píše BONUS v jeho [[http://naucte-se.haskell.cz/rekurze|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.
~~DISCUSSION~~