Funkcionální programování - Výrazy a definice

V seriálu o funkcionálním programování pokračujeme druhou částí, ve které si všimneme základních elementů, z nichž se skládají funkcionální programy.

Funkce a operátory

Základní způsob, jak vytvářet složitější výrazy z jednodušších, je aplikace funkce na argumenty. Aplikaci funkce f na argumenty x, y, z zapisujeme:

f x y z

Obecně mohou na místě argumentů i funkce stát libovolné výrazy. Pokud je argumentem proměnná, není nutno ji uzavírat do závorek.

V mnoha jazycích, jako třeba C nebo Java, se rozlišuje mezi uživatelsky definovanými funkcemi, pojmenovanými identifikátorem, a mezi operátory, pojmenovanými zvláštním symbolem (+, *, &&, ||) a s infixovou syntaxí pro aplikaci takových operátorů na argumenty. Moderní funkcionální jazyky umožňují uživatelské definice funkcí i operátorů.

V souladu s terminologií jazyka Haskell budeme operátorem nazývat binární funkci, jejíž jméno nezačíná písmenem. Například (+), (-), (*), (/), (^) budou běžné aritmetické operátory, (==), (/=), (<), (<=), (>), (>=) relační operátory, a (&&), (||) booleovské operátory.

Uvedený prefixový tvar aplikace však není vždy pohodlný. Proto v případě binárních operátorů budeme kromě prefixového zápisu aplikace

(+) x y

používat též infixový zápis

x + y

Navíc, u asociativních binárních operátorů můžeme vynechávat nadbytečné závorky a využívat obvyklých priorit, takže třeba

(+) ((*) ((*) 1 2) 3) ((*) 3 4)

lze zapsat přehledněji:

1 * 2 * 3  +  3 * 4

Prefixově zapsaná aplikace má při výpočtu přednost před infixovou: f x+y je totéž jako (f x) + y.

Všimněme si, že odkazujeme-li se na operátory samostatně (např. vystupují-li ve výrazu jako argumenty vyšších funkcí apod.), uvádíme je v kulatých závorkách. V infixově zapisované aplikaci je uvádíme bez závorek. Naopak binární funkce (jejich jméno je alfanumerické a začíná malým písmenem) uvádíme bez závorek a jejich aplikaci píšeme obvykle prefixově. Při alternativním infixovém zápisu je uvádíme v obrácených apostrofech.

21  `lcm`  6
lcm  14    21
2006 `mod` 491
mod  1992  50

Lokální­ definice

Kdybychom byli při vytváření výrazů odkázáni pouze na pevně danou malou množinu konstant a funkcí, byly by naše vyjadřovací schopnosti silně omezené. Proto téměř všechny jazyky umožňují definovat nové konstanty a funkce.

Jestliže chceme ve výrazu použít nějaký podvýraz vícekrát, např.:

(pi/2) * x  +  (pi/2) * y

můžeme v něm lokálně zavést novou proměnnou d:

let  d = pi/2  in  d * x  +  d * y

Části výrazu mezi let a in říkáme definice.

Nově definované proměnné (nalevo od rovnítka) jsou vázány na výrazy (napravo od rovnítka) a jsou použitelné v části výrazu za in. Těchto lokálních definic může být v rámci jednoho výrazu let i více naráz a mohou být použity i na pravých stranách definic:

let  a = 3
     b = 4
     c = 5
     s = (a+b+c)/2
in  s*(s-a)*(s-b)*(s-c)

Alternativně můžeme lokální definice zapisovat pomocí konstrukce where. Ta se od výrazu let liší tím, že lokální definice je uvedena až za výrazem, v němž je použita.

f x y  =  d * x  +  d * y  where  d = pi/2

p s  =  s*(s-a)*(s-b)*(s-c)  where  s = (a+b+c)/2

Druhý rozdíl spočívá v tom, že konstrukce where může stát jen v nadřazené definici, zatímco let je výraz a může být tedy podvýrazem libovolného výrazu.

Definovat můžeme i funkci. Kromě jejího jména zapíšeme nalevo od definičního rovnítka i 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)
u .-. v  =  if u>v then u-v else 0

Poslední řádek definuje operátor (.-.). Ekvivalentní způsob zápisu je

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

Podstatným důvodem, proč definice zvyšují naši vyjadřovací sílu, je fakt, že definice mohou být rekursivní:

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

Globální definice a skripty

Řekli jsme, že definice za slovem where mají jen lokální působnost – vztahují se pouze na podvýraz před where. Často bývá pohodlné definovat si nové funkce i globálně – pro všechny výrazy, s nimiž pracujeme v programu. Proto je v Haskellu také možnost definovat konstanty a funkce i globálně. Definice se zapíší do zvláštního souboru – skriptu.

Například napíšeme-li do souboru priklad.hs definici faktoriálu

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

a spustíme interpret pomocí hugs priklad.hs, můžeme pak ve svých výrazech funkci fact používat.

Definice podle vzoru

Na místě formálních parametrů funkcí a operátorů nemusejí vystupovat jen proměnné. Obecně zde jsou tzv. vzory. 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. Například výše uvedenou definici funkce fact lze pomocí vzorů zapsat takto:

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

Častým vzorem, jak je vidět z těchto příkladů, je konstanta. Takový vzor vyhovuje pouze jedinému skutečnému argumentu – tomu, jenž je roven právě této konstantě. V tomto příkladě to je 0 v prvním řádku definice. Naopak vzor, kterým je proměnná, vyhovuje všem argumentům. To je případ druhého řádku definice. V našem příkladě případ, že argument funkce fact je nulový, vyhovuje oběma řádkům definice. Proto, aby taková definice byla korektní, dohodneme se, že se při výpočtu použije vždy první větev definice, jejíž vzory vyhovují skutečným argumentům funkce. V uvedeném příkladě se tedy první větev definice bere pro nulový argument a druhá větev pro všechny ostatní, tedy nenulové argumenty.

Podobně funkci sumsq pro výpočet součtu čtverců (z úvodní části) lze zapsat i takto:

sumsq 1  =  1
sumsq n  =  n*n + sumsq (n-1)

Jiným příkladem mohou být definice booleovských operátorů, v nichž vzory jsou opět booleovské konstanty nebo proměnné.

False && x  =  False
True  && x  =  x

False || x  =  x
True  || x  =  True

not True   =  False
not False  =  True

Vzory však nemusejí být jen konstanty a proměnné. Obecněji je vzor výraz, jehož žádný podvýraz nelze redukovat – skládá se pouze z proměnných a tzv. konstruktorů. Konstanty jsou vlastně nejjednoduššími konstruktory – jsou to konstruktory arity 0. Konstruktorem arity 2, tedy binárním konstruktorem, je například konstruktor (,) uspořádaných dvojic. Můžeme ho využít třeba v haskellovských definicích:

fst (x,y) = x
snd (x,y) = y

Další konstruktory poznáme v části o datových strukturách.

Shrnutí

• Výrazy se skládají z aplikací funkcí a operátorů na argumenty a z lokálních definic.
• Globální definice zavádějí nové funkce a konstanty, které pak platí ve všech použitých výrazech.
• Definice mohou být rekursivní.
• Funkce lze definovat pomocí vzorů – výrazů popisujících možné tvary skutečných argumentů.