Függvények, operátorok
Függvények megadása, curry-forma
A függvények típusának megadása típuskifejezésekkel történik, Curry-formában(Ha Curry-formában gondolkozunk, akkor belátható, hogy lényegében minden operátor egyváltozós. Indok: vegyük pl.: a 3+4 kifejezést. Ezt értelmezhetjük úgy, hogy először vesszük a 3+ -t, ami annyit jelent hogy a majd megadott argumentumhoz hozzáad hármat. Gondoljunk a C vagy C++-ból ismert ++ operátorra, csak itt egy helyett hárommal növelünk. Így, ha megadjuk a (3+)-nak 4-et, akkor a négyet megnöveljük hárommal. Ez a többi operátorral is végiggondolható, ezért mondhatjuk, hogy Curry értelmezése alapján minden operátor egyváltozós.). Ez, ha úgy tetszik, a függvény prototípusa. Ennek azonban nem kell a függvény meghívásának helyén már ismertnek lennie, mivel a Haskell a Hindley-Milner rendszerrel kiszámítja a megfelelő típust - tehát csak annyi a feltétel, hogy a kiszámított típus ne ütközzön a megadottal. Mi több, a prototípust egyáltalán nem is kötelező megadni. Persze jobb, ha mégis kiírjuk, hogy ellenőrizhessük, valóban jól írtuk meg, és jól is használjuk a függvényt.
A Haskell függvények leképezés típusúak, azaz a deklarációjukban legkülső szinten szerepel egy vagy több "->" (pl. Integer -> [Integer] -> String, de nem [Integer -> Integer]). Ha a függvény deklarációjában szerepel sablon (polimorf) típus, akkor sablon (polimorf) függvényről beszélhetünk. Egy függvényt két módon lehet definiálni.
Példa:
fv [paraméterek] = [kifejezés]
vagy a lambda-kalkulushoz közelebbi alakban:
fv = (\[paraméterek] -> [kifejezés])
Minden kétváltozós függvény írható infix és nem infix alakban is: a szimbólum azonosítójú függvények nem infix alakja ([függvény]), a szöveges azonosítójú függvények infix alakja pedig `[függvény]`, azaz
(+) 3 5 ugyanaz, mint 3 + 5 és
max 4 3 ugyanaz, mint 4 `max` 3
Függvényeket többször is lehet definiálni, ezek közül az első megfelelő fog kiértékelődni, ezért figyelni kell rá, hogy a speciális eseteket írjuk előbb. Így pl. a nem negatív dekrementálás:
delta 0 = 0
delta x = x - 1
Ez igazából nem más, mint a már korábban ismertetett case több sorban, tehát az előző definíciót írhatnánk így is:
delta x = case x of { 0 -> 0; _ -> x - 1 }
Ahogy már láttuk, bonyolult kifejezések esetén használhatunk őrfeltételeket, illetve egyszerűsíthetünk a let és where kulcsszavak használatával.
Speciális függvény a bot = bot, ez jól láthatóan végtelen rekurzió, "értékét" _|_ (bottom)-al jelöljük. Ez a Haskell szinonima a futási idejű hibára; az I/O monadon kívül (ami kivételeket használ) minden hiba ezt az értéket adja. Ennek segítségével jól meg lehet figyelni a lusta kiértékelést: ha pl. a "c x = 0" függvényt "c bot" paraméterezéssel hívjuk meg, 0-t ad vissza, nem kapunk hibát. A függvények (nevezetesen az adatkonstruktorok) lusta kiértékelésnek köszönhető az is, hogy készíthetünk végtelen adatstruktúrákat
pl. a Fibonacci sorozat:
fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]
ahol a zip a két sorozatból párok sorozatát állítja elő, tehát
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip xs ys = []
Kompozíció
Függvények kompozícióját képezhetjük a (.) (infix) operátorral, ez a következő függvény:
(.) :: (b->c) -> (a->b) -> (a->c)
f . g = \x -> f (g x)
Mintaillesztés
A mintaillesztés során a föggvényt helyettesítjük a függvény törzsével, egészen addig amíg el nem érjük a normálformát. A kiértékelési stratégia, azaz a redex-ek (reducible expressions) kiválasztási sorrendje Haskell esetén lusta kiértékelésű. Ez azt jelenti, hogy a kifejezés (rész)eredményét nem feltétlenül kell ismernünk, hogy megkapjuk a végeredményt. Ha egy kifejezés egyik tagjából már következik valami, akkor felesleges a másik tagját kiértékelni, mivel az már nem befolyásolná a végeredményt. Pl.: igaz || (hamis || igaz). Már az első igazból következik, hogy az állítás igaz, független a zárójeles tagtól, ezért az a rész már ki sem értékelődik.
Függvények kiértékelésénél az aktuális paramétert a fordító/interpreter megpróbálja a formális paraméterhez illeszteni, és az első illeszkedő definíciót használja. Ezt, ahogy fent is láthattuk, befolyásolják az őrök, az if/then/else illetve a case kifejezések. Ezenkívül a formális paraméter lehet adatkonstruktort használó kifejezés is, pl. a
head (x:xs) = x
definíció használja a lista adattípus konstruktorát, a ":"-ot (ez megtehető a felhasználó (programozó) által definiált konstruktorok esetén is).
Van, hogy kényelmes lenne az egész paraméterre is hivatkozni, ezt az "@" (as) segítségével tehetjük meg, pl.
f (x:xs) = x:x:xs helyett
f s@(x:xs) = x:s -t írhatunk.
A "_" mindent helyettesít, ez a wildcard karakter, így pl. a head definíciója:
head (x:_) = x
Ha egy függvényt definiálunk, akkor nem feltétlen kell megadnunk a szintaxisát, a fordító ki fogja következtetni. A Haskellben a felhasználó is definiálhat többszörösen terhelt függvényeket, sőt, a meglévő, többszörösen terhelt függvényeket kiterjesztheti újabb típusokra.
Függvény definíció esetén sokszor a zárójelek elszaporodása csökkenti az átláthatóságot. A Haskellben ezt megelőzően használható a $ jel, ami egy zárójelet takar a sor végéig. Tehát a $ egy szintaktikus cukor, valójában maga is egy infix operátor, amely egy függvényt és egy paramétert vár, és eredménye a függvény(paraméter) kifejezés. Ám mivel precedenciája nagyon alacsony így a fenti hatást is eléri, azaz
f(g(h(x)))
kifejezés ekvivalens a következővel:
f $ g $ h $ x
Kiértékelés (lusta/mohó)
Mint már említettük a függvények kiértékelése lusta módon történik. Tehát az argumentumok kiértékelését próbálja minél inkább elhalasztani. Arról is volt szó hogy néha hatékonysági szempontból nem megfelelő a lusta kiértékelés. Szerencsére a Haskell lehetőséget ad kérésünkre a mohó kiértékelése. Ehhez használhatjuk a seq függvényt, melynek jelentése:
seq:: a -> b -> b
seq _|_ b = _|_
seq a b = b, if a != _|_
Ez a függvény ha az a kiértékelés után értelmes eredményt ad végrehajtja a b-t. A megértéshez, és átláthatósághoz be van vezetve a $! mohó kiértékelő operátor
f $! x = x ’seq’ f x
Azaz tehát a $! ha értelmes az argumentum kiértékelése, akkor a függvény eredményét adva vissza, kijátszva ezzel a lustaságot.
Rekurzió
A rekurzió az amikor egy függvény közvetlenül, vagy közvetve önmagát hívja (utóbbi esetén kölcsönös rekurzióról beszélhetünk). Rekurzió esetén fontos hogy a függvény esetszétválasztó legyen a paraméterei tekintetében, különben könnyen végtelen rekurzió lehet (általában mintaillesztéssel, őrfeltételekkel, illetve if ..then .. else konstrukcióval érik el). Figyelni kell továbbá hogy ne legyen túl mély, mivel míg imperatív nyelvek esetén az aktivációs rekordok megtöltik a végrehajtási vermet, a funkcionális nyelvek esetén a lusta kiértékelés miatt egyre bővülő kifejezés lehet már túl nagy. Egy egyszerű példa rekurzióra:
fact 0 = 1
fact n = n * fact (n-1)
Mi is történik a fact 2 hívására?
fact 2 => 2 * fact 1 => 2 * 1 * fact 0 => 2* 1 * 1
Itt meg is állhatnánk mondván ezen ismeretekkel már bárki tud rekurzív függvényeket írni. Ami igaz is, de sajnos nem mindenki tud jó rekurzív függvényeket írni, ami hatékonyan bánik a memóriával és a processzoridővel.
„Vég” rekurzió (tail recursion), összesítő paraméter (accumulating parameter)
Azt nevezzük „vég” rekurzióak (tail recursion) amikor egy függvény paramétere a rekurzív hívás végeredménye. Példa NEM ilyen függvényekre:
naiveSumList (x:xs) = x + (naiveSumList xs)
naiveSumList [] = 0
len [] = 0
len (x:xs) = len xs + 1
Mi lehet a probléma a fenti definíciókkal? Működésük helyes, ám de nézzük a következő lefutást:
naiveSumList [3, 4, 5, 6] =>
3 + (naiveSumList [4,5,6] =>
3 + (4 + naiveSumList [5,6])) =>
3 + (4 + (5 + (naiveSumList [6]))) =>
3 + (4 + (5 + (6 + (naiveSumList [])))) =>
3 + (4 + (5 + (6 + 0))) =>
3 + (4 + (5 + 6)) =>
3 + (4 + 11) =>
3 + 15 =>
18
Látható hogy a függvény kibontott változata nagyon sokáig él a kibontáshoz képest, nem redukálható vissza, mert sajnos meg kell várnia a rekurzív hívás eredményét, ami szintén erre vár. Miközben szép lassan fogy a memória (például a len 1 millió hosszú listára már stack overflow-al jár), és ráadásul lassú is (len 0,20 sec 20 ezer hosszú listára). Jó lenne valahogy elérni, hogy hamarabb ki lehessen értékelni részformulákat. Erre egy jó módszer hogy összesítő paraméterrel „vég” rekurzióvá alakítjuk a fenti függvényeket:
sumList lst = sumLoop lst 0 where
sumLoop (x:xs) i = sumLoop xs (i+x)
sumLoop [] i = i
len' [] acc = acc
len' (x:xs) acc = len' xs (1 + acc)
len xs = len' xs 0
Mit nyertünk ezzel?
sumList [3,4,5,6] =>
sumLoop [3,4,5,6] 0 =>
sumLoop [4,5,6] 3 =>
sumLoop [5,6] 7
=> sumLoop [6] 12 =>
sumLoop [] 18 =>
18
Azaz most jóval hamarabb részeredményekhez jutunk, és nem kell a memóriát a kifejezés tárolására használni, hanem elég csak a részeredményt. Ezáltal gyorsul is a függvény, (például a len 20 ezer hosszú listára 0,02 sec).
Mohó vagy lusta stratégia
Ha valaki figyelt észrevehette hogy még van egy kis csalás. Ugyanis a lusta kiértékelés miatt még az összesítő paraméter valójában a rekurzió végéig nő: (0+3+4+5+6) [jobb esetben a fordító optimalizálására a (+) mohó]. Így érdemes lenne explicit rávenni a mohó kiértékelésre (csak a megváltozott sorok):
sumLoop (x:xs) i = sumLoop xs $! (i+x)
len' (x:xs) acc = len' xs $! (1 + acc)
Rekurzió egyszerűbben
Fentebb láthattuk, hogy hatékony rekurziók megírása nem egyszerű feladat. Ám de a standard könyvtárban rengeteg hasznos hatékony rekurzív függvény van, melyek használatával egyszerű és hatékony kódot kapunk. Nem véletlenül szokás a faktoriális példánál profi megoldásnak nevezni a következő egysoros kódot:
fact n = product [1..n]
Magasabbrendű függvények
Míg imperatív nyelvekben csak a magasabb szintű tárgyalás során kerül sor az alprogramra mutató hivatkozásra, a funkcionális világban az egyik legtermészetesebb dolog, hogy függvényeknek függvény is lehet paramétere (hiszen minden függvény). Ezt nevezzük magasabbrendű függvényeknek. Használatuk, és hasznosságuk a quicksort példáján keresztül:
quickSort [x] = [x]
quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
where less = filter (< x) xs
equal = filter (== x) xs
more = filter (> x) xs
Ez maga a quicksort algoritmus definíciója. Használatkor csak a neve után írunk egy listát olyan típusú elemekből, melyek az Ord típusosztályba tartoznak (azaz a szükséges műveletek definiáltak). De mi van akkor ha a [„hello”, „World!”] bemenetre hívjuk meg a függvényt? Elsőre meglepő módon felcseréli a sorrendet (ugyanis az szokásos kódolásokban „W” előbb van mint „a”). Lehet hogy ez a programozó célja, de nem biztos, így célszerű lenne valamilyen módon lehetőséget adni a programozónak a döntésre (és a rugalmasságra, ugyanis néha lehet hogy éppen visszafelé sorrend, illetve más rendezés kell). Jobban belegondolva a rendezéshez (lásd Ord típusosztályban a compare függvény) csak egy Ordering kimenetű (LT, EQ, GT egyike) két paraméteres függvény kell. Ez a függvény is lehet a quicksort paramétere:
quickSort _ [] = []
quickSort c (x : xs) = (quickSort c less) ++ (x : equal) ++ (quickSort c more)
where less = filter (\y -> y `c` x == LT) xs
equal = filter (\y -> y `c` x == EQ) xs
more = filter (\y -> y `c` x == GT) xs
Ezután már általánosabban lehet használni a quicksort függvény:
usual = compare --az Ord osztályból
descending a b = compare b a
dictionary = [„hello”, „World!”, „Let”, „use”, „Haskell.”]
quicksort usual dictionary --az előző rendezés
quicksort descending dictionary --visszafelé sorrend
quicksort insensitive dictionary –nagybetű független (ha definiáltuk az insensitive-t)
Talán a legjellegzetesebb példa magasabbrendű függvények használatára a map, mely egy függvényt és egy listát vár, és eredménye egy lista, melyben a függvény eredményei állnak a bemenő lista elemeire:
map :: (a -> b) -> [a] -> [b]