Haskell Hero

Funkci v krabičkovém modelu znázorňujeme krabičkou. Přesněji krabičkou, do které něco vhodíme, zatřepeme a ono z ní něco vypadne.

Mějme třeba funkci red, do které hodíme válec, ona jej obarví na červeno a dá nám jej jako výsledek.

Znázornění funkce red

My budeme pracovat s funkcemi, které zpracovávají nejčastěji čísla nebo seznamy. Například funkci (+) dáme dvě čísla a ona nám dá jejich součet.

Znázornění funkce (+)

Základem funkcionálního programování jsou definice vlastních funkcí.

Definice funkce má dvě části, levou a pravou, odděleny znakem rovnítka.

• Levá část se skládá ze jména funkce a jejích formálních parametrů. Parametry se zapisují řetězci znaků začínajících malým písmenem, nejčastěji jen malým písmenem.
• V pravé části je napsán výsledek vyhodnocení funkce po jednom kroku.

Příklad:

Definujte funkci plus3, která vezme tři čísla a vrátí nám jejich součet. Chceme, aby se její aplikace například na čísla 5, 1 a 2 vyhodnotila takto:

plus3 5 1 2  ~>  5 + 1 + 2  ~>*  8

Její definice by mohla vypadat následovně:

plus3 x y z  =  x + y + z

Příklad:

obvodObdelnika 5 3  ~>  2 * (5 + 3)  ~>*  16

Po zaměnění skutečných parametrů 5 a 3 za formální parametry a a b dostáváme obecnou definici:

obvodObdelnika a b  =  2 * (a + b)

Příklad:

Definujme funkci cisloSlovem, která si bude brát jeden argument – celé číslo.

• Pokud dostane číslo 1, vrátí řetězec "Jednicka".
• Pokud dostane číslo 2, vrátí řetězec "Dvojka".
• Pokud dostane nějaké jiné číslo, vrátí řetězec "Neznam".

Jedna možnost, jak ji zadefinovat by byla následující:

cisloSlovem x = if x == 1 then "Jednicka"
                          else if x == 2 then "Dva"
                                         else "Neznam"

Jak bude Hugs postupovat při vyhodnocování výrazu cisloSlovem 2, je zřejmé. Za x dosadí 2 a nahradí výraz cisloSlovem 2 pravou stranou definice, čili výrazem:

if 2 == 1 then "Jednicka"
          else if 2 == 2 then "Dva"
                         else "Neznam"

if 2 == 2 then "Dva"
          else "Neznam"

Druhou možností je definovat funkci podle vzoru. Ta stejná funkce bude definována podle vzoru následovně. Jednotlivé řádky definice se nazývají klauzule.

cisloSlovem 1 = "Jednicka"
cisloSlovem 2 = "Dvojka"
cisloSlovem x = "Neznam"

Hugs bude v tomto případě při vyhodnocování výrazu cisloSlovem 2 postupovat následovně:

• Zkusí, zda se dá cisloSlovem 2 dosadit do levé strany první klauzule cisloSlovem 1. Nedá, pokračuje na druhou klauzuli.
• Zkusí, zda se dá cisloSlovem 2 dosadit do levé strany druhé klauzule cisloSlovem 2. Ano, dá.
• Výraz cisloSlovem 2 se přepíše na pravou stranu druhé klauzule, čili na výraz "Dvojka".

Jak by se vyhodnotil výraz cisloSlovem 5?

• Dá se cisloSlovem 5 dosadit do cisloSlovem 1? Nedá, zkusíme druhou klauzili.
• Dá se cisloSlovem 5 dosadit do cisloSlovem 2? Nedá, zkusíme třetí klauzili.
• Dá se cisloSlovem 5 dosadit do cisloSlovem x? Ano, dá.
• Za x se dosadí 5 a výraz cisloSlovem 5 se nahradí pravou stranou třetí klauzule, což je "Neznam"

Jelikož není proměnná x na pravé straně vůbec použitá, místo x můžeme napsat _ (podtržítko), což znamená sem se může dosadit cokoli, co bude následně zapomenuto. Naše funkce by tedy vypadala takto:

cisloSlovem 1 = "Jednicka"
cisloSlovem 2 = "Dvojka"
cisloSlovem _ = "Neznam"

Hugsu při vyhodnocování nezáleží na pořadí definic funkcí ve skriptu. To znamená, že pokud do skriptu napíšeme

krat 0 _ = 0
krat x y = plus y (krat (x - 1) y)

plus x y = x + y

krat x y = plus y (krat (x - 1) y)
krat 0 _ = 0

Příklad:

Definujte funkci soucet, která si bude brát přirozené číslo a vrátí součet všech přirozených čísel, které jsou menší nebo rovny zadanému číslu. Příklad vyhodnocení:

soucet 3  ~>*  3 + 2 + 1  ~>*  6

Se znalostí definice podle vzoru můžeme funkci soucet pro čísla 1 až 5 definovat následovně:

soucet 1  =                  1
soucet 2  =              2 + 1
soucet 3  =          3 + 2 + 1
soucet 4  =      4 + 3 + 2 + 1
soucet 5  =  5 + 4 + 3 + 2 + 1

My ale potřebujeme obecnou definici, která by umožnila výpočet funkce soucet nad všemi přirozenými čísly. V tuto chvíli přichází na řadu rekurze.

Pěkné znázornění, co to rekurze je, můžete najít na české necyklopedii. Stručně řečeno, rekurzivní funkce je funkce, která se vyhodnotí na výraz obsahující sebe samu.

Pokud se podíváme na definici soucet 4, zjistíme, že se skládá z funkce (+), argumentu 4 a výrazu 3 + 2 + 1, který se dá zapsat jako soucet 3. Takto můžeme zapsat všech pět klauzulí:

soucet 1  =  1
soucet 2  =  2 + soucet 1
soucet 3  =  3 + soucet 2
soucet 4  =  4 + soucet 3
soucet 5  =  5 + soucet 4

Z tohoto zápisu už můžeme odvodit obecný zápis funkce soucet:

soucet x  =  x + soucet (x - 1)

Pokud si ale necháme vyhodnotit výraz soucet 3, Hugs bude chvíli počítat a nakonec napíše, že mu přetekl zásobník. Proč k tomu došlo? Zkusme si rozepsat vyhodnocení výrazu soucet 3:

soucet 3

~>  3 + soucet 2
~>  3 + 2 + soucet 1

~>  3 + 2 + 1 + soucet 0
~>  3 + 2 + 1 + 0 + soucet (-1)
~>  3 + 2 + 1 + 0 + (-1) + soucet (-2)
~>  ...

soucet 1  =  1
soucet x  =  x + soucet (x - 1)

Poznámka

Jelikož je rekurze ve funkcionálním programování hojně využívaným prvkem, již existuje velké množství knihoven s funkcemi, které rekurzi řeší za nás. Z těchto většinou jednoduchých funkcí pak můžeme skládat funkce složitější.

Už víme, jak definovat vlastní funkci. Jak ale říct její definici Hugsu? Máme dvě možnosti. Můžeme ji definovat buďto lokálně, nebo globálně. V tomto odstavci se podíváme na lokální definici.

Lokální definice se zapisuje jako v tomto tvaru:

let definice in výraz

Příklady:

let pet  =  5 in 5 + pet  ~>  5 + 5  ~>  10
let plus3 x y z  =  x + y + z  in  plus3 1 3 5
    ~>  1 + 3 + 5  ~>*  9

Pokud potřebujeme definovat více než jednu funkci nebo konstantu v jednom let-výrazu, uzavíráme je do složených závorek a oddělujeme středníky.

let {dva = 2; tri = 3; pet = 5; plus3 x y z = x + y + z}
    in plus3 tri pet dva
~> 3 + 5 + 2 ~>* 10

Druhá varianta lokální definice je lokální definice s where. Vypadá následovně:

výraz where definice

Příklad:

plus3 1 3 5  where  plus3 x y z  =  x + y + z