====== 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~~