• Egy természetes szám lehet 0 (0-s eset),
• vagy egy másik természetes számot követő természetes szám (indukciós lépés).

A célja ennek a rövid matematikai kitérőnek az, hogy könnyebbé tegye a Haskell-beli listák ehhez hasonló rekurzivitásának megragadását, felfogását. A megfelelő két eset listák esetén:

• Üres lista
• Nem üres lista, mely tartalmaz egy elemet, meg a maradék listát (ez utóbbi lehet üres lista).

A teljes definíciókhoz ismernünk kell még egy fontos függvényt, amely "összeragasztja" az elemeket listává. Ennek jele a (:), kiejtve "cons", mint konstruktor. A típusa a következő:

és így működik

Tehát a két eset, amely lehetővé teszi a listák rekurzív megadását:

Ez azt jelenti, hogy egy lista vagy üres, vagy tartalmaz egy elemet és egy azt követő listát (ami megint csak lehet üres ...). Az a típusváltozó arra utal,hogy bármilyen típusú listaelemeink lehetnek[4]. A lista struktúrája nem függ a benne tárolt adatok típusától. Az egyetlen megkötés az, hogy egy lista minden eleme azonos típusú kell, hogy legyen. A listánk állhat egész számokból, Boolean értékekből vagy lebegőpontos számokból, de nem vegyíthetjük a típusokat. Ennek a definíciónak a segítségével már írhatunk listákon működő függvényeket is, például egy olyan függvényt, amely meghatározza a lista elemeinek összegét:

Az első elemet rekurzívan elválasztjuk a többitől egészen addig, amíg üres listánk nem marad. Üres listára pedig tudjuk az eredményt: nulla. Ezek után a lista elemeit fordított sorrendben vesszük és összeadjuk, azaz az utolsó elemet adjuk hozzá először a nullához, és így tovább. Ha minden elemen végigmentünk, akkor megkaptuk a lista elemeinek összegét.

A lista-konstruktort arra is használhatjuk, hogy újraírjuk a lista n. elemét kiolvasó függvényünket:

3.2 A listák alapvető függvényei

3. táblázat: hasznos függvények listák kezeléséhez

Számos fontos függvény áll rendelkezésünkre, ha listákkal akarunk dolgozni. A 3. táblázat ezek közül mutat be néhányat, valamint röviden megmagyarázza, mit is csinálnak.

A függvények némelyike (mint pl. a map) különösen érdekes, mivel egy függvény az argumentumuk - ezeket a függvényeket magasabb rendű függvényeknek hívjuk. A következőkben néhány ilyen függvényt fogunk alkalmazni.

3.2.1 Kódold a nevedet ASCII számokká és vissza (a map használata)

Tegyük fel, hogy adva van egy sztringünk és szükségünk van minden karakterének az ASCII kódjára. A sztring egy karakterlista a Haskell-ben, így kézenfekvő a lista-függvények alkalmazása a feladat megoldásakor. Az ord függvényt kell minden egyes karakterre alkalmazni, az megadja a hozzájuk tartozó ASCII számot. Mivel a sztring egy karakterlista, ennek az ASCII számokká való kódolásához az ord függvényt minden egyes karakterre alkalmaznunk kell. Ebben lesz segítségünkre a map. A map típusdefiníciója:

A map függvénynek két argumentuma van, egy függvény és egy lista, és egy listát ad vissza. A bemeneti lista elemei tetszőleges a típusúak, az eredmény lista elemei pedig szintén tetszőleges b típusúak. Az első argumentumként szereplő függvénynek van egy a típusú paramétere és egy b típusú értékkel tér vissza. A példánkban az a típusnak a karakter felel meg, a b típusnak pedig az egész számok típusa. A map implementációja:

Az f függvényt rekurzívan alkalmazza a lista minden elemére és egy új listát készít belőlük a lista konstruktorának alkalmazásával (':').

Ezek után a függvényünk a következőképpen írható meg:

A definíciós fájlt újra betöltve a Hugs-ba, már tesztelhetjük is az új függvényünket:

Az eredmény:

3.2.2 Sokszög területének kiszámítása

Tegyük fel, hogy egy sokszög területét kell kiszámolnunk. A sokszög tulajdonképpen x és y koordinátákkal adott pontok listája. A területre vonatkozó Gauss formula szerint:

Számoljuk hát ki a területet a lista-függvények segítségével! A sokszög definiálásával kell kezdenünk. A mi esetünkben ez egy pontokból álló lista, ahol minden egyes pont egy koordinátapáros. A teszteléshez majd a következő sokszöget használhatjuk (azonnal látszik, hogy a területe 10000):

A p függvény egy egyszerű sokszöget ad vissza, amelyet tehát majd a függvényünk tesztelésére használhatunk.

Először azt kell végiggondolnunk, hogy hogyan építsük fel a listánkat ahhoz, hogy a lista-függvények könnyen alkalmazhatóak legyenek rajta. Az egyértelmű, hogy az utolsó lépés a részterületek összegzése lesz és a kettővel való osztás. A foldl függvény az lista elemeinek egy megadott függvény szerinti egyesítését adja, egy megadott kezdőértékkel számolva. Ha össze akarjuk adni az elemeket, akkor a '+'-t kell használnunk. Mivel a '+' definíció szerint két argumentuma között áll (x+y), '(+)'-nek kell itt írnunk. A '(+) x y' kifejezés ugyanaz, mint az 'x+y'. A függvényünk kezdőértéke legyen nulla. Tehát a függvény a következőképpen nézhet ki:

Most a részterületek (xi+ x(i+1))(yi+ y(i+1)) kiszámítására kell találnunk egy módszert. Szeretnénk, ha lenne négy listánk az alábbi tartalommal:

4. táblázat: eredménylisták Így a zipWith segítségével ki tudnánk számítani a részösszegeket. A zipWith függvény a következőképpen definiálható (a függvény nevét zipWith'-re változtattam, hogy elkerüljük a konfliktusokat az amúgy már definiált függvénnyel):

Az első sor a függvény típusát definiálja. A függvény bemenetként kap két listát és egy függvényt (a listák elemeinek egyesítési módjának leírására). A következő két sor leállítja a rekurziót, ha bármelyik lista kiürült. Az utolsó sor írja le a függvény működését. Fogja a listák első elemeit és alkalmazza rájuk az f függvényt. Az eredmény a kimeneti lista egy eleme lesz.

A Gauss-formula megvalósításából már csak egy rész maradt ki: vegyük az első pont x koordinátáját és vonjuk ki belőle a második pont x koordinátáját (xi + x(i+1)). Ha a 4. táblázat listáit használjuk, akkor az első lista elemeit vesszük és kivonjuk belőlük a második lista elemeit. Így a

sorral elvégezhetjük a kivonást a listák összes elemére. Ezek után a teljes formula a következőképpen alakul:

Az egyetlen fennmaradó probléma a 4. táblázat listáinak előállítása. Az 1. és a 3. lista igen egyszerű, ugyanis azok a pontok x illetve y koordinátái. A map segítségével két új függvényt, az fts-t és az snd-t alkalmazhatjuk a sokszög pontjainak eredeti listájára. Az fst függvény fog egy párt és visszaadja annak az első tagját. Az snd hasonlóan működik, csak a pár második tagját adja vissza. Ha feltesszük, hogy a koordináták (x,y) sorrendben adottak, akkor az 1. és a 3. listát a következőképpen kaphatjuk meg:

Itt a poly a sokszöget megadó lista. Mivel a (4)-es formula akkor is működik, ha felcseréljük x-et és y-t, nem számít, hogy a sokszög pontjainak koordinátái milyen sorrendben vannak megadva.

A két másik lista előállítása már egy kicsit bonyolultabb. Mindkét esetben a lista el van forgatva. Tehát fognunk kell az első elemet és a lista végére kell fűznünk. Erre egy lehetőség:

A head és függvények a listát két részre bontják: az első elemre (head) és a maradékra (tail), ami maga is egy lista. Ha egy kifejezés köré szögletes zárójeleket rakunk, akkor abból listát csinálunk, aminek az eleme maga a kifejezés lesz [5]. A ' ++ ' függvény (vagy concat, mint konkatenáció) fog két listát és egyesíti őket úgy, hogy a második lista elemeit az első lista utolsó eleme után fűzi.

A fenti kódrészletek kombinációja kiadja magát a végső függvényt, amelybe még hibakezelést is építettünk erre az esetre, ha háromnál kevesebb pontot kapna a függvény bemenetként (akkor nincs terület):

3.3 Egyéb hasznos listakezelő függvények

Mint arról már a 3.2 részben is volt szó, a függvényeknek lehet függvény argumentumuk is. Erre példa a map függvény, amelyet a 3.2.1 részben használtunk:

A függvénydefinícióhoz nem kell explicite tudnunk, hogy milyen típusokat használunk. Futásidőben azonban fontos, hogy már mindkét típust ismerjük. Futásidőben már konkréten létező adatokkal dolgozunk, amelyeknek meghatározott típusaik vannak, így ekkor már ismerjük a paraméterek típusait. Az eredmény típusának azonban egyértelműnek kell lennie. Ebben az esetben specifikálnunk kell a kívánt eredmény típusát a ':: Type' hozzáadásával.

A következő fontos és megismerendő függvény a filter (szűrő). Átnevezve implementáltuk a már definiált függvénnyel való ütközés elkerülése végett:

A szűrő függvénynek két argumentuma van. Az első egy függvény (maga a szűrő), a második egy tetszőleges a típusú lista. A szűrő kap egy listaelemet és egy Boolean éréket ad vissza. Ha ez az érték True, akkor az adott elem a listában marad, máskülönben nem fog szerepelni az eredménylistában.

3.4 Másodfokú egyenletekből álló lista gyökeinek számítása

Van egy másodfokú egyenletekből álló listánk (valós számhármasokként tárolva, mint a 2.3-as részben). A feladat két részre oszlik. Biztosítanunk kell, hogy minden egyenletnek valósak a megoldásai, mert ha komplex megoldások adódnának, akkor a függvényünk hibaüzenetet adna. Tehát szükségünk van egy olyan függvényre, amely True-t ad vissza, ha a gyökök valósak és False-t, ha a gyökök komplexek:

A fenti függvényt használhatjuk azoknak az egyenleteknek a kiszűrésére, amelyek gyökei valósak:

A ps függvény egy két másodfokú egyenletet tartalmazó listát ad vissza. Az első egyenletnek (p1) valósak a gyökei, míg a másodiknak (p2) komplexek. A newPs függvény a real függvény segítségével kigyűjti ps-ből azokat az elemeket, amelyeknek valósak a gyökei. Végül a rootOfPs a roots függvényt alkalmazza a listában maradt egyenletekre. Az eredmény tehát az egyenletek megoldásainak listája lesz.

Feladat: Alkalmazd a komplex gyököket számoló függvényt (az előző feladatból) másodfokú egyenletek listájára!

3.5 Alternatív függvénydefiníció

Egy függvényt mindig többféleképpen is meg lehet írni. A különbségek általában a definíció absztrakciójában jelennek meg vagy a felhasznált függvények halmazában. A speciális eseteket is többféleképpen lehet kezelni. A következő példában egy lista hosszának a kiszámolására definiálunk függvényeket. Bár igen eltérően néznek ki, mégis ugyanazt az eredményt adják. Az absztrakció minden esetben egyforma (minden függvénynek van egy [a] típusú paramétere és egy Int típusú eredménye).

A speciális eset ebben a feladatban az üres lista esete. Az üres lista hossza nulla. Az l1, l2l3 függvények ebből a tényből indulnak ki és iteratívan számolják ki a lista hosszát. A különbség az, hogy másképpen detektálják az üres listát:

• Az l1 mintaillesztést alkalmaz,
• az if-then-else elágazást használ,
• az "őröket" használ (ld. 6.2).

Az l4, l5 l6 függvények más-más lista-függvényeket hívnak segítségül a számoláshoz:

• Az l4 először minden listaelemet 1-re cserél. majd egyszerűen összeadja a lista elemeit.
• Az definiál egy lokális függvényt, amely agy lokális számlálót léptet és a foldl függvény segítségével megy végig a listán.
• Az l6 az l5-höz hasonlóan jár el, csak a függvény egy lambda-kifejezésben definiálja[6].

3.6 Összefoglalás

Ebben a fejezetben a listákkal foglalkoztunk. A legfontosabbak még egyszer:

• A listák tökéletesek tetszőleges számú elem együttes reprezentálására, feltéve, hogy az elemek azonos típusúak.
• Sok hasznos listákkal foglalkozó függvény található a prelude.hs-ben.
• A magasabb rendű map függvény egy adott függvényt alkalmaz egy lista minden elemére.
• A rekurzió alapvető elméleti háttere a matematikai indukció.
• A rekurzió az imperatív programozás hurkait helyettesíti matematikai úton.
• A listák izomorfak a valós számokkal és így a rekurziót is ugyanúgy alkalmazhatjuk rajtuk.
• A map, filter, foldl/foldr függvények a listákat kezelő függvények közül a legfontosabbak és sok alkalmazásban igen hasznosak.
• Általában többféleképpen lehet egy függvényt Haskell-ben definiálni.

4. Adatreprezentáció

Eddig csak az alapvető típusokat használtuk függvényeinkben. Általánosságban szükségünk lehet adatstruktúrák definiálására, hogy azokban tároljuk megfelelő formában a függvényünknek szükséges adatokat.

4.1 Típusszinonimák

Folytassuk a másodfokú egyenleteket megoldó példát! A bemenet egy hármas (Float,Float,Float), a kimenet egy pár (x1,x2). A roots függvényre a típusszignatúra így nézett ki:

Ha a programunkban több függvény is lenne, akkor az a fajta típusinformáció nem sokat segítene annak megértésében, hogy mint csinál ez a függvény. Jobb lenne valami következőt látni:

Ezért s Haskell támogatja a típusszinonimákat. A szinonimák felhasználok által megadott nevek már létező típusokra illetve azokból álló többesekre és listákra. A

sorok azt jelentik, hogy ezután minden Float-okból álló hármasra hivatkozhatunk a Poly2 néven, a szintén Float-okból álló párokra pedig Roots2 néven. Mindekét elnevezésre igaz, hogy többet mondanak a típusról, mint az eredeti többesek leírása (a Poly2 névből megtudhatjuk, hogy egy másodfokú polinom együtthatóiról van szó, a Roots2 pedig nyílván egy ilyen polinom gyökeit tárolja).

Összegzés: A típusszinonimák csak már létező típusokhoz biztosítanak elérést. Céljuk, hogy világosabbá tegyék egy program működését illetve azt, hogy egy adott függvénynek mik e bemenetei és kimenetei.

4.2 Felhasználók által definiált adattípusok

Előre definiált típusok (Bool,Int,FloatChar) összeépítése listákba ([])vagy többesekbe (pár, hármas, ...) sokszor bizonyul nagyon hatékony megoldásnak a legkülönbözőbb feladatoknál. Mégis néha saját definíciókra van szükségünk:

• Többesek kényelmesebb formában: Poly = (Float,Float,Float)
• Felsorolás típusok: pl. a hét napjai
• Rekurzív típusok: Num (N0) vagy nulla, vagy a Num-ra következő elem

A felhasználók által definiált adattípusok fontos szerepet játszanak az osztályalapú programozási stílusban, ezért érdemes megtanulnunk, hogyan működnek.

Magyarázat:

• Az adattípus definiálást a data kulcsszóval kezdjük
• A típus neve Polynom (ez hordozza a típusinformációt)
• A Poly a konstruktor függvény (próbáld ki a ':t Poly'-t)
• A első, második és harmadik argumentumának típusa

Ezek után újraírhatjuk a roots függvényt roots2 néven (hogy elkerüljük az ütközést):

A -5.0 körüli zárójelek a pTwo definícióban ezért kellenek, mert a negatív számok jelölésére használt jel megegyezik a kivonás jelével. A zárójelek nélkül az interpreter félreértené a kódot és a következő hibaüzenetet generálná:

A legfontosabb, hogy jól meg tudjuk különböztetni a típus nevét (Polynom) a konstruktortól (Poly). A típusnév mindig a típusinformációval kapcsolatos sorokba kerül (amelyek tartalmazzák a '::'jelet), a konstruktor pedig az alkalmazással kapcsolatos sorokba (amelyek tartalmazzák a '=' jelet). A típuskonstruktor az egyetlen függvény, amelynek nagy betűvel kezdődik a neve és az egyetlen olyan, amely a kifejezések baloldalán is szerepelhet.

A konstruktor neve megegyezhet a típus nevével, de ez nem ajánlott.

Fontos! Végül egy kis szintaktikai cukor. Hogy elkerüljük a függvények eredményeinek kiíratásával kapcsolatos problémákat, csak két szót kell minden új adattípus definíciójához hozzátennünk: deriving Show. így automatikusan generálunk a Show osztályból[7] egy példányt az új adattípusunk számára.

A következő kódrészlet a rekurzív adattípusra ad példát. Próbáld ki a parancssorban!

4.3 Paraméteres adattípusok

Az adattípusokat típusparaméterekkel lehet paraméterezni, melyeknek a típus használatakor már példányosítottnak kell lenniük. Ilyen adattípusra egyszerű példa a lista:

Ezzel a listát mint rekurziót definiáltuk. A kezdőérték az üres lista. Minden más listának van egy eleme, ami lista feje és egy farka, ami maga is lista. A lista elemei tetszőlegesek, de azonos típusúak. Néhány példa:

5. Polimorfizmus

Polimorfizmusról akkor beszélünk, ha egyetlen függvény többféle argumentumtípusra is alkalmazható. Tipikus példa erre más programozási nyelvekben az összeadás és kivonás művelete. Általában a következő kifejezések vonatkozhatnak egészekre és lebegőpontos számokra is. C++-ban azt mondanánk, hogy a függvények "túlterheltek".

5.1 Ad hoc polimorfizmus

Ha két műveletnek csak ugyanaz a neve, akkor ad hoc polimorfizmusról beszélünk. Ez igazából zavaró eset, hiszen két különböző művelet, különböző tulajdonságokkal használhatja ugyanazt a nevet (pl. a '+' sztringek összefűzésénél nem kommutatív: a + b nem egyenlő b + a). Ez így nem szerencsés, a programozóknak nagyon oda kell figyelniük, hogy elkerüljék az ebből adódó hibákat (pl. az kód olvasója mást vár a '+'-tól, mint ami annak a programbeli szerepe).

5.2 Részhalmaz polimorfizmus

A polimorfizmus egyik gyakori fajtája az adattípusok egy részhalmaz relációján alapul. Vegyünk alapul egy teljesen általános típust (mondjuk a számokat), amelyből altípusok konstruálhatóak (Integer, Float, stb.). Ezek után azt mondjuk, hogy az összeadás művelete a szám típus minden objektumára alkalmazható, tehát az altípusaira is.

Altípus relációk nem definiálhatóak közvetlenül a Haskell-ben. Az azonban egy lehetséges követelmény, hogy a használt adattípushoz létezzenek specifikus osztály-példányok. A roots példában valós számokra van szükségünk paraméterként és eredményként is. Mivel a valós számok implementálása nem lehetséges számítógépes rendszerekben, közelítésekkel kell dolgoznunk (pl. lebegőpontos számok). Emellett megkövetelhetjük, hogy bizonyos függvények - összeadás, szorzás, gyökvonás, ... - legyenek definiálva az éppen használt adattípusra. Ezek a függvények a Haskell Num (számok),Fractional és Floating osztályaiban vannak definiálva. Tehát elegendő megkövetelni a Floating implementációját:

A '(Floating a) =>' hozzáadása nem generálja a szükséges példányt! Csak leellenőrizheti a példány létezését futásidőben (amikor már egyértelmű, hogy melyik adattípust is használjuk) és generálhat hibaüzenetet (Unresolved Overloading), ha a szükséges példány nem létezik.

5.3 Paraméteres polimorfizmus

A fenti problémára a Haskell-ben használt megoldás a 'paraméteres polimorfizmus'. Egy művelet

alkalmazható minden olyan szituációban, ahol az a paraméter konzisztensen ugyanarra a típusra van cserélve, mint pl.:

vagy

Ennek megfelelően az adattípusoknak is lehetnek típus paramétereik (pl.: data List a).

Ez jó lehetőségeket biztosít, mert a műveleteket általános formában is ki lehet fejezni, a választott paraméter sajátságaitól függetlenül. Például meg lehet nézni egy lista hosszát anélkül, hogy tudnánk, milyen típusú elemeket is tartalmaz.

6. Haladó programozási módszerek

6.1 Kompozíció

Legutóbbi példánkban két függvényt alkalmaztunk egy listára. Ennek a matematikai kifejezésére az f (g(x)) szolgál. Vagy azt is írhatjuk, hogy (g°f )(x). A legfontosabb feltétel az, hogy a 'g' függvény eredményének típusa egyezzen meg az 'f ' függvény argumentumának típusával. A Haskell-ben ez igen hasonlóan működik. A kompozíció operátora a '.', amely fog két függvényt és összekapcsolja őket ((f . g) x = f (g x)).

A pont operátor helyettesíti a matematikában használatos kör operátort. A filter real függvény felel meg a g függvénynek, a map roots az f-nek, az x változó pedig jelen esetben a ps.

6.2 Őrök

Az őrökkel if-then-else kifejezéseket lehet másképpen leírni. Tegyük fel, hogy adva van az alábbi példánk:

Őrök használatával ugyanez a következőképpen nézne ki:

Ha az első teszt (d > 0) True-t ad vissza, akkor az eredmény d, ha nem, akkor a második sor feltételét ellenőrizzük. Az eredmény ekkor nulla. Az otherwise kifejezés a harmadik sorban egy előre definiált kifejezés a Haskell-ben, mely minden esetben True-val tér vissza. így tehát ha az első két sor ellenőrzése False-szal tér vissza, akkor a függvény eredménye egy hibaüzenet lesz. Látható tehát, hogy a tst2 eredménye minden esetben megegyezik a tst1 eredményével.

Az őrök nagyon hasznosak lehetnek nem folytonos, szakaszos függvényeknél. Tegyük fel, hogy van egy függvényünk, amely értéke negatív számokra -1, a nullára 0, pozitívokra pedig 1 (azaz a signum függvény). A függvény matematikai definíciója a következőképpen néz ki:

Ez őrökkel felírva (a nevet sign-re változtattuk a már létező signum függvénnyel való ütközés elkerülése végett):

Látható, hogy csak apró különbségek vannak a matematikai jelölés és a Haskell szintaxis között: függőleges vonalkák helyettesítik a kapcsos zárójelet, valamint a feltétel és az eredmény fordított sorrendben szerepel.

6.3 Szekciók

A standard numerikus függvényeknek két argumentumuk van és egyetlen eredményük:

Alkalmazásuk a következőképpen történik:

de így is írhatnánk:

Ha az első argumentumot az operátorral együtt specifikáljuk, akkor a típusszignatúra:

Más szavakkal az '(+)' első argumentumát "megette" a 3-as szám. Ez a tulajdonság map-es konstrukcióknál lehet hasznos:

Az egyenlőség (==) és a rendező operátorok (<, <=, >, >=) egy másik olyan függvényhalmazt alkotnak, mely széleskörűen alkalmazott a szekciós formában. Mivel Boolean értéket adnak vissza eredményként, az ő szekciójuk a filter-es konstrukciókban válik hasznossá:

Figyeljük meg az operátor és az argumentum megváltozott helyzetét ebben a szekcióban! Szimmetrikus operátorok esetén nincsen különbség, de a sorrendező operátoroknál van. Próbálgasd a következőket a 'filter p [1,2,3,4]'-ban a p helyén és figyeld meg, mi történik:

Ősszegzés: Szekciók használatával egy meglévő függvényt olyan új függvénnyé lehet konvertálni, amelynek kevesebb argumentuma van, mint az eredetinek volt. Gyakran használják olyan függvények létrehozására, amelyek alkalmasak a map, a filter és a függvénykompozíció bemeneti függvényeként szerepelni.

6.4 Lista felfogások

A lista felfogások még egy eszközt az eddigiek mellé, amivel listákat lehet definiálni és műveleteket végrehajtani rajtuk (általában megtalálható a funkcionális programozásról szóló tankönyvekben). A forma teljesen természetesen adódik, ha a listákra a halmazok fogalmai szerint gondolunk.

A halmazelméletben a 0 és 100 közé eső páratlan számokat a következő halmaz reprezentálja: {x | x Î 0..100, x páratlan}. A funkcionális nyelveken ez így írható:

Tehát a kapcsos zárójelek helyére szögletesek kerülnek, az 'Î' jel helyére a '<-' jel és máris szinte bármilyen kifejezést definiálhatsz halmazként.

Például ha egy lista minden elemét meg akarjuk szorozni egy másik lista minden elemével, akkor a következő függvényt írhatjuk:

A map és filter függvényeket is ki lehet így fejezni:

7. Funkcionális programozás vs. imperatív programozás

Példa: vektorok skaláris szorzatának számítása. Legyenek a és b egydimenziós vektorok, a elemei a1, a2, ..., an, b elemei b1, b2, ..., bn. A skaláris szorzatuk a megfelelő komponensek szorzatainak összege:

Imperatív programban ez valahogy így nézne ki:

Több olyan hely is feltűnhet, ahol hiba lehetséges. Szükségünk van egy változóra a részeredmények tárolásához. Ez a változó az egész függvényen belül aktív lesz és így máshol is használható. Ez nehezen olvashatóvá teheti a programot és hibákhoz is vezethet, ha a programozó nem elég elővigyázatos. A vektor elemeinek számát már a for-do hurok előtt meg kell adnunk, mivel az a hurok második paramétere. Végül megjegyzendő még az, hogy elveszítjük a kapcsolatot a matematikai jelöléssel :

Egy funkcionális programban többféle megoldást is választhatunk. Itt van az egyik legrövidebb és legelegánsabb:

Sok furcsának tűnő dolog van ebben a két sorban. Ha eltekintünk a Num a => -től, akkor az első sor tiszta. Ez a rész megmondja az interpreternek, hogy a tetszőleges a típusnak számnak kell lennie. A Num egy osztály, amelyben összeadó, kivonó, szorzó, stb. függvények találhatók. Nincs szükségünk nem szám típusokra is megadni ezt a függvényt. Tehát az adat szám típusú, ha a Num-nak van annak típusára implementációja. Tehát az interpreter ezt ellenőrzi.

A második sorban nincs a függvénynek paramétere. A teljes sor így nézhetne ki:

Ha összevetjük az '=' jel bal- és jobboldalát, akkor láthatjuk, hogy mindkét esetben az x az utolsó elem. Ilyen esetben következmények nélkül elhagyhatjuk a kérdéses paramétert. Ez nem csak azt jelenti, hogy kevesebbet kell gépelnünk, hanem azt is lehetővé teszi, hogy az igazán fontos részekre koncentráljunk - magára az algoritmusra.

A második sorban három függvény kompozíciója szerepel:

• uncurry zip: a zip függvény két listát kap paraméterként és egyesíti azokat a következőképpen: fogja az első elemet mindkét listából és pár képez belőlük. Ez lesz az eredménylista első eleme. Aztán fogja mindkét lista második elemét, azokból is pár képez (ez lesz az eredménylista második eleme), stb. Az uncurry függvény úgy módosítja a zip függvényt, hogy nem két külön bemenő listája lesz, hanem egy pár. Az uncurry használatára később még mutatunk példát (ut függvény).
• map (uncurry (*)): ez a rész fogja az első lépésben keletkezett többeseket és megszorozza azok elemeit. Egyetlen többesre az uncurry (*) is elég lenne a művelet elvégzéséhez. A map függvény azért kell, hogy a művelet végrehajtódjon minden egyes többesen.
• foldr (+) 0: végül ez a függvény adja össze a szorzások eredményeit.

A jobb megértés érdekében próbáld ki az alábbi példákat és figyeld meg, mit csinálnak:

A következő lépés a függvény kiterjesztése vektorok listájára. Tehát a függvényünk bemenő paramétere legyen vektorok (azaz egész számok listája) listája. Az eredmény a vektorok skaláris szorzata lesz:

Az innXa és innXb függvények ugyanazt csinálják. Mindkettő három részből áll. A különbség csupán az, hogy az innXb a foldr1 függvényt használja a foldr helyett. A foldr1 a paraméterként szereplő függvényhez definiált neutrális elemet használja. Szorzás esetén ez 1, összeadás estén pedig 0.

A transpose függvény listák listáját kapja paraméterül és egy új listák listáját állít elő. Az első lista a bemeneti listák első elemeit tartalmazza, a második lista a bemeneti listák második elemeit tartalmazza, stb.

A következő példával tesztelhetjük függvényünket:

Nézzük tehát, hogy milyen előnyeit fedeztük fel a funkcionális programozásnak az imperatív programozással szemben:

• Csak a saját argumentumain dolgozik (nincsenek mellékhatások).
• Hierarchikus, azaz egyszerű függvényekből építkezünk.
• Olyan függvényeket használ, amelyek általában más programokban is hasznosak lehetnek.
• Statikus és nem ismétlődő.
• Teljesen általános.
• Nem ad nevet az argumentumainak.

8. Egyszerű adatbázis építése

Az adatbázis azonosítókkal és attribútumokkal ellátott elemek gyűjteménye. Azonosítóként egész számokat fogunk használni. Ezeknek egy adatbázison belül egyedieknek kell lenniük. Az attribútumok értékhalmazokhoz ('név', 'kor', 'szín') értékeket ('John', '1211', 'red') rendelő függvények.

A szükséges műveletek:

• insert (beszúr egy új objektumot néhány attribútummal az adatbázisba)
• select (azaz kiválasztás, adott azonosítóhoz visszaadja az objektumot)
• selectby (feltételes kiválasztás, azaz a feltételeket kielégítő objektumokat adja vissza)

A specifikáció-kifejtési eljárás vizsgálata a célunk: Tetszőleges adattípusokat tartalmazó szignatúrákkal definiáljuk a függvényeket és csoportosítjuk őket. Az eredménycsoportok az úgynevezett osztályok. Később majd definiáljuk ezeket a függvényeket specifikus adattípusokra is (osztályok példányai).

Alapértelmezett definíciókat adunk meg általános műveletekre, amelyek nem függnek az implementációs részletektől - len a 3.1-es fejezetben.

Ha így dolgozunk, akkor az osztályainkat különböző programozók is használhatják, munkájuk eredményei kompatibilisek lesznek egymással (bár az implementációk eltérhetnek).

Az egyszerűség kedvéért bevezetünk két típusszinonimát az azonosítókra és az attribútumokra. Az azonosító egy Integer Az attribútum két sztringből áll, ezek közül az első az attribútum típusát adja meg, a második pedig az értékét.

Az Objects osztály az objektumok viselkedését definiálja. Definíció szerint egy objektum tartalmaz egy ID típusú azonosítót és egy Attrib típusú attribútumokból álló listát. Bizonyos műveletek (object: létrehoz egy új objektumot; getID: visszaadja az objektum ID-jét; getAttrib: visszaadja az objektum attribútumait) implementáció-függőek, ezért egy példányban definiálni kell őket használat előtt. De például a getName művelet (a "név" attribútum értékét adja vissza) nem függ az implementációtól, ezért használhatjuk az alapértelmezett definícióját (egy axióma).

A Databases osztály az objektumok egy gyűjteményének viselkedését specifikálja. Nem lényeges, hogy milyen típusú az objektum feltéve, hogy vannak arra a típusra műveletek definiálva az Objects osztályban. Az első öt művelet, csak úgy, mint ez előbb, függ az implementációtól.

Most már megvan egy egyszerű adatbázis teljes specifikációja. A következő lépés egy implementáció elkészítése a specifikáció tesztelésére. Az itt bemutatott megoldás csak egy a sokféle lehetséges közül:

Először is az objektumok egy részletes reprezentációjára van szükségünk. Definiáljuk az Object adattípust (azonosítóval és attribútumokkal) és az Object osztályhoz kötjük, azaz implementáljuk az osztályt erre a típusra. Csak azokat a függvényeket kell implementálnunk, amelyekre nincs axiómánk az osztálydefinícióban.

Látható, hogy minden implementáció-függő függvénynek szoros kapcsolata van az adattípussal. A függvények vagy kiolvasnak egy adatot az adathalmazból és azt adják vissza eredményként, vagy adatot írnak az adathalmazba és magát az adathalmazt adják vissza eredményül. Tehát nem nehéz ezeket a függvényeket implementálni. A komplex feladatok (mint pl. egy specifikus attribútum olvasása) az osztálydefiníciók részei.

Az adatbázissal is hasonlóan kell eljárnunk. Az adatbázis adathalmaza egy azonosítóból és objektumok listájából áll. Az adathalmazban tárolt azonosító az utolsó azonosító, amelyet egy objektum használt, ezért könnyű egy új objektumra az azonosító kiszámolása:

Most már elkezdhetjük az adatbázis tesztelését. Tesztelési célra ilyen jellegű példákat használunk:

A tesztek a választott implementációhoz kapcsolódnak.

9. Modulok

Az eddigi programok rövidek és tömörek voltak, ráfértek volna egyetlen lapra is. Ha komolyabb programokat szeretnénk írni, akkor nagyon valószínű, hogy a programjaink mérete meg fog nőni. Egy hosszú fájl áttekintése pedig nehéz feladat. Ezért hosszú projekteket inkább olyan részekre bontunk, amelyek szorosan összetartozó programrészleteket tartalmaznak. Ezeket a részegységeket moduloknak hívják (nem csak a Haskell-ben).

Hogyan írjunk modult? Ez igazán egyszerű, csak egy sort kell beírnunk a module kulcsszóval és az aktuális modul nevével (nagy kezdőbetűvel!), utána a where kulcsszót és ennyi az egész. Jegyezzük meg, hogy ennek a sornak a Haskell szkript első olyan sorának kell lennie, ami nem megjegyzés vagy üres sor. Egy példa:

Néhány hasznos konvenció:

• Egy fájlba pontosan egy modult rakj!
• A moduloknak és a fájloknak legyen azonos a nevük!

Tehát a fenti példát Test.hs néven érdemes fájlba menteni.

Csak a Haskell definíciók összegyűjtése jól elnevezett modulokba még nem biztosítaná azt a kifejező erőt, amit el akarunk érni. A legfontosabb, hogy megtanuljuk, hogyan lehet más modulokban levő definíciókat a konkrét modulunkba importálni. Importálhatunk függvényt a számos Haskell könyvtárból és a saját korábbi, modularizált munkáinkból is. A továbbiakban mindkettőre mutatunk példát.

9.1 Már létező definíciók importálása

A modulkezelés gyakorlására jó feladat egy olyan, már definiált függvénynek a használata, amelyet nem a prelude.hs biztosít nekünk. Példaként tekintsük a sort függvényt, amely a '\hugs\Lib\List.hs' szkriptben van definiálva. Ki kell kötnünk, hogy a List modult (meglepetésre éppen úgy hívják, mint a 'List.hs' szkriptet) importáltuk a saját modulunkba.

Ments el egy modult 'Test01.hs' néven és töltsd be a Hugs-ba! Figyeld meg, mely fájlok töltődnek be. Ha azt a kellemetlen hibaüzenetet kapnánk, hogy "module List not previously loaded", akkor gépeljük be, hogy ":s i+", üssük le az ENTER-t az interpreterben és az üzenet nem jelenik meg újra.

9.2 Fájlok összekapcsolása projektté

Van egyszerű szabály az importált modulok deklarálásának írásakor: minden modulban importálni kell azokat a modulokat, amelyeknek függvényeit használja a definíciójában.

Ha a moduljaink teljese függetlenek, akkor lehet, hogy egyetlen projektfájlba importáljuk az összes többi fájlt a következőképpen:

ahol a deklarációs részek az alábbiak:

Általában néhány függvényt minden modul használ. Ilyen esetben minden modulban importálni kell azt a modult, ahol az adott függvény definiálva volt. Egy példa:

Egyszerűen ellenőrizheted, mi történik, ha lefelejted az egyik import-sort. Csak tedd megjegyzésbe a második sort a 'Part02.hs'-ben és töltsd be újra a 'Project.hs' fájlt! Biztosan hibaüzenetet fogsz kapni.

Összegzés: A modularizáció számos okból előnyös a funkcionális programozásban. A programegységek kisebbek lesznek és ezáltal könnyebben kezelhetőek; a különböző modulok közötti kapcsolatok átláthatóak, világosak a későbbi felhasználás és a hibakeresés során is; valamint csak a projektfájl betöltésével kényelmesen betölthető az összes felhasznált fájl.

Felhasznált irodalom:

[1] A "Hello" egy sztring. A Pascal-hoz hasonlóan a Haskell is idézőjelekkel adja meg egy sztring elejét és végét. Az egyedülálló karakterek aposztrófok között vannak. Sztring: "abc"; karakterek: 'a', 'b', 'c'.
[2] A windows-os verzióban használhatod a script (szöveg) menedzsert új fájlok betöltésekor - csak válaszd az 'Add script'-et (szöveg hozzáadása), válaszd ki a fájlt, majd kétszer klikkelj az 'Ok' gombra. Ha a DOS-os verziót használod, akkor meg kell változtatnod az aktuális elérési útvonalat (path) (':cd ...') és töltsd be a fájlt a következő utasítással: ':l "FileName.Ext"'.
[3] Ha Pascal függvényt írnánk, ezt így olvasnánk: function Increment (i : Integer) : Integer
[4] Ezt a koncepciót polimorfizmusnak hívják. Bővebb információk az 5. részben.
[5] vagy elemei, ha több kifejezést rakunk szögletes zárójelek közé vesszőkkel elválasztva
[6] Ebben a segédletben nem mutatjuk be a lambda-kifejezéseket. Ez a definíció csak azért került a többi közé, mert a Haskell beépítetten ezt a definíciót használja.
[7] Az osztályokról és példányaikról ld. bővebben a 8. fejezetben.