Obsah

AP6, IN6 Rekurze
Co byste ještě měli znát?
Předměty
Použitá literatura
Kam dál
Vypracoval
Diskuze

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římá rekurze nastává, pokud funkce volá přímo sama sebe.

Příklad přímé rekurze

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.

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 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 , 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.¹⁾

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

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. ²⁾

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

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

Funkce lze definovat také pomocí vzorů. Vzor popisuje množinu argumentů, které tomuto vzoru vyhovují. Deﬁnice funkce se pak rozpadá na více větví, klausulí. Při výpočtu se pak z deﬁnice 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ů.⁴⁾

Rekurzivní deﬁnici funkce fact lze pomocí vzorů zapsat

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

FI:IB015 Úvod do funkcionálního programování (jaro), RNDr. Libor Škarvada

Použitá literatura

RNDr. Libor Škarvada, Cvičení k předmětu
RNDr. Libor Škarvada, 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 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.

¹⁾

miniskripta, kapitola 6, strana 29

²⁾

Miniskripta – zápisky z přednášek, kapitola 6, strana 26

³⁾

Miniskripta - zápisky z přednášek, kapitola 6, strana 26

⁴⁾

miniskripta, kapitola 2, strana 9

Diskuze

Zdeněk Kedaj, 2008/06/11 16:28

Jaký je rozdíl mezi operátorem a funkcí? Mě to přijde stejné. Až na to, že funkce se musí při infixovém zápisu obalit apostrofy a operátory se při prefixovém zápisu musí obalit do závorek. Taky by mě zajímalo, co je to ten „kombinátor“. Zatím to chápu jako funkci obecně využitelnou k definici jiných funkcí.

Roman Plášil, 2008/06/12 16:58

Žádný rozdíl tam není. Jen asi syntaxe Haskellu rozlišuje funkce pojmenované alfanumerickými znaky od funkcí pojmenovaných pomocí speciálních symbolů (+, *, …), aby se to nepletlo.

Marek Babák, 2008/06/15 10:41

Nejde ani tak o Haskel, obecně při programování speciálním symbolům říkáme operátory, takže operátor = funkce nadefinovaná pomocí speciálního symbolu (!@#$%^&*+-.<>:/?|~…)

Jitka Pospíšilová, 2008/06/11 21:38

ja jsem tak osobne kombinator take pochopila z toho, co mi rikal pan Skarvada, mela by to tedy byt obecne (a v kontextu teto otazky) funkce, ktera je pouzita k definici jine funkce. Tema na kombinatory a jejich vyuziti je dale rozvijeno napr. v Lambda kalkulu, tam je dle wiki ¹⁾ jako kombinátor oznacovan uzavreny lambda vyraz; nektere kombinatory pak maji primo oznaceni: S, K, I, B, C, Y (kombinátor pevného bodu), takze mozna se na urovni znalosti z predmetu Uvod do funkcionalniho programovani neda jen tak lehce kombinator definovat a asi by melo stacit jej proste chapat jako funkci vyuzitelnou k definici jinych funkci.

¹⁾ http://cs.wikipedia.org/wiki/Lambda_kalkul

Zdeněk Kedaj, 2008/06/12 08:37

ok, diky za reakci

petr nehyba, 2008/06/14 15:35

dotaz: proc je curry zaprasana takto:
curry :: ((a,b) → c) → a → b → c
curry g x y = g (x,y)
a ne takto?:
curry :: ((a,b) → c) → a → b → c
curry g (x,y) = g x y
// unika mi nejaka podstatna myslenka ? pripada mi ze v prikladech je funkce pouzita spravne ale definovana spatne..(ac ve slidech je to popsano stejne)

Marek Babák, 2008/06/15 10:39

curry ti z nižší funkce udělá funkci vyšší, tj. přesně jak je tam napsáno, pokud máš funkci s pevným počtem parametrů např. g(x,y), tak funkce curry ti z ní udělá vyšší funkci která nemá pevný počet parametrů, takže definice musí být g x y = g(x,y) - to ti říká, že funkci g můžeš zadat libovolný počet parametrů a funkce g se postará o jejich aplikaci do g(x,y)

Dusan Katona, 2008/06/15 18:14

Toto inak ani ja presne nechapem, logicky mi tiez vyplyva, ze to ma byt ten 2.sposob, ktory uvada Petr Nehyba…V tom prvom mi nesedi typ s definiciou…vysvetlite mi to niekto viac po lopate?:)

Adam Libuša, 2008/06/16 17:09

Toto aj mňa dosť dlho miatlo, ale je to snáď jasné ako to trošku pre lepšie pochopenie uzátvorkujem:

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

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

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

Vysvetlím to na prvom prípade. Najprv skús ignorovať argumenty x a y. Funkcia curry sa aplikuje na funkciu g a vznikne funkcia, ktorá je už potom schopná prijať dva argumenty, namiesto dvojice a pritom má funkčnosť funkcie g(x, y).

Karel Barot, 2008/06/16 18:16

Zkusim trosku rozepsat ten priklad s funkci add:
add x y = x + y
add2 (x,y) = x + y

k dispozici mame pouze funkci add2 a chceme z ni udelat funkci add. K tomu slouzi funkce curry:

curry add2 x y = add2 (x+y)

jako prvni parametr ji dame jmeno funkce, kterou chceme volat a parametry.

Funkce curry se postara o to, aby se parametry daly do n-tice tak, jak to vyzaduje funkce add2:
curry add2 5 4 → add2 (5,4)

coz je presne predpis funkce curry, pokud si za add2 dosadis g a za 5,4 x,y.

Dusan Katona, 2008/06/16 18:46

Dakujem pani, uz je to jasnejsie :)

petr nehyba, 2008/06/17 05:54

zacinam se chytat…
….matouci je pro me prave to ze…
funkce1 = f x y je primo
funkce2 = f (x,y) je primo
funkce3 = G ocekavajici x, dale ocekavajici y = curry funkce2 x y
tedy curry aplikovano na funkce2 nevytvori funkci1 ale funkci3…. pak funkce1 a funkce3 nejsou stejne ale na danych argumentech vrati stejny vysledek…tedy z hlediska vysledku jsou stejne :))))
curry tedy nezrusi seznam promennych v argumentu funkce2 (jak jsem si puvodne myslel) ale vytvori NOVOU funkci ktera POCKA na vlozeni ostatnich argumentu do seznamu pro onu NIZSI funkci2 …rozdil funkce3 a funkce1 je pak v tom ze funkce3 ceka na argumenty -pro funkci2 kdezto funkce1 nic takoveho neresi, je trivialni….
VYSSI je pak funkce3 nad funkci2… funkce1 neni v tomto oznacena (ani jako vyssi nebo nizsi)? nebo ji lze brat jako VYSSI?
PS jestli se nepletu tak takto polopate by to melo byt napsano od zacatku a nemusel bych se ja (idiot) nad tim zabyvat :)

Adam Libuša, 2008/06/25 02:26

Jj, v podstate to je tak ako si napísal. funkce1 a funkce3 sú potom na rovnakej úrovni a obe sú vyššie ako funkce2.

Karel Barot, 2008/06/22 04:15

dist f g x = f x (g x)

Nema tam bejt nahodou dist f g x = f (g x)?

Dusan Katona, 2008/06/22 06:59

na f (g x) nepotrebujes definovat novu funkciu dist, lebo to je . (po)

You could leave a comment if you were logged in.

home/inf/ap6.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru