B. A Glasgow Haskell Compiler B.1. Haskell Platform . . . . . . . . . . . . . . . . . B.2. Nyelvi kiterjesztések . . . . . . . . . . . . . . . B.2.1. A kiterjesztések engedélyezése és tiltása . B.2.2. A jegyezetben alkalmazott kiterjesztések
73 73 74 74 75
ii
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1. fejezet Rövid áttekintés Ebben a fejezetben szeretnénk egy rövid áttekintést adni a tisztán funkcionális programozás alapvető fogalmairól. A téma mélysége és a könnyű olvashatóság fenntartása miatt itt most szándékosan nem törekedtünk a teljes részletességre. Ezért a most következő összefoglalás egyaránt alkalmas lehet arra, hogy adjon egy átfogó, vázlatos képet a témával elsőként találkozóknak, illetve mindazok számára, akik korábban már foglalkoztak vele, de szeretnék ismereteiket újra feleleveníteni. A későbbi fejezetekben az itt említett fogalmakat, megoldásokat újra elő fogjuk venni és majd kimerítőbben tanulmányozzuk.
1.1. Bevezetés A funkcionális programozás a deklaratív programozási paradigma egyik ága. Ekkor programjainkat mint függvény- és típusdefiníciók vegyes sorozatát adjuk meg. Ezek a definíciók aztán dominók sorozatához hasonlóan gyakran egy hosszú láncot alkotnak, melyet az egyik végéről meglökve a programunk végül lefut, ahogy az egymásra támaszkodó elemek eldőltik egymást. Ez a folyamat egészen addig tart, amíg akad az, olykor sokfelé ágazó, láncban ledönthető dominó. A funkcionális nyelvi programok esetében a lánc eldőlthető végét start kifejezésnek nevezzük, ez lesz lényegében a főprogramunk. A dominók eldőlése a definíciók, legtöbbször függvények értékének meghatározását, kiértékelését jelenti, és amikor egy összes ledönthető dominó végül eldőlt, megkapjuk a programunk végeredményét. Azonban érdemes megjegyezni, hogy a funkcionális programok számos tekintetben eltérnek a dominók sorozatától, gyakran képesek a valós világban lehetetlen trükköket végrehajtani. Például bizonyos elemeknek neveket adhatunk, amelyekre később minden olyan helyről tetszőleges mennyiségben 1
hivatkozhatunk, ahova beilleszthetőek anélkül, hogy több példányt gyártanánk belőlük. Vagy készíthetünk olyan sorozatot, ahol a dominók egy része újra feláll, és ezzel ismét eldönthetővé válnak. Ezáltal kapunk egy olyan sorozatot, ahol a dominók sosem fognak véglegesen eldőlni. Ez utóbbiak felelnek meg a végtelen sokáig futó programoknak. Másrészt a funkcionális programokban, ellentétben a népszerűbb, ún. imperatív programozási nyelvi programokkal, a szerző nem azt írja le, hogy az egyes részek pontosan mikor és milyen sorrendben dőljenek el. Helyette mindössze csak szabályokat ad meg erre vonatkozóan, de a tényleges folyamatot már nem irányítja közvetlenül. Ezért nevezzük tehát ezt a programozási stílust deklaratív, vagy leíró jellegű programozásnak. A deklaratív gondolkodási mód a fentiek révén nagy szabadságot ad a programozónak, amelyek segíti abban, hogy a megoldandó problémákat egy viszonylag absztrakt és matematikai oldaláról fogalmazza meg, egyfajta képletek, összefüggések alkalmazásával. Ezek így gyakran hozzájárulnak ahhoz, hogy a megoldásban kialakuljon egy rendszer, és hogy a fejlesztés során ne vesszünk el olyan könnyen a részletekben. Maga a képletszerű megfogalmazás egyébként rögvest függvénydefiníciók formájában jelenik meg, például így: negate x = 0 - x Ez a függvény egy szám előjelét fordítja meg úgy, hogy kivonja nullából. A neve annak angol nyelvű elnevezéséből fakadóan most negate, valamint egyetlen paramétere van, ez az x. A függvény nevét és paraméterét annak definíciójától, vagyis törzsétől egy = (egyenlőségjel) választja el, így ezzel lényegében egy egyenletet kapunk. Ezeket az egyenleteket fogjuk arra felhasználni, hogy eljussunk a programunk végeredményéhez. Ennek során tulajdonképpen nem kell mást csinálnunk, mint helyettesítenünk az egyenlet bal oldalán szereplő programrészletet annak jobb oldalán szereplő megfelelőjével úgy, hogy közben értéket adunk a paramétereknek. Ekkor azt is állíthatjuk, hogy a függvényünk eredménye csak és kizárólag annak bemenetétől függ, ilyen függvényeket szokhattunk meg a matematikában is. Ezeket tiszta függvényeknek nevezzük, ezek következetes alkalmazásából származik a funkcionális programozás egyik ága, a tisztán funkcionális programozás. Az iménti függvénydefiníciót úgy tudjuk felhasználni, ha elhelyezzük egy szöveges állományba, amelyet most nevezzük úgy, hogy Tutorial.hs. A .hs kiterjesztés utal arra, hogy ez egy Haskell nyelvű forrásprogram. Ezt például a Glasgow Haskell Compiler (GHC) interaktív felületén keresztül tudjuk megszólítani, ha betöltjük értelmezésre a ghci nevű programba. Windows 2
rendszerek esetében ehhez elegendő csak duplán kattintani az állomány nevére. Így a következő eredményt kell kapnunk: $ ghci Tutorial.hs GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Main ( Tutorial.hs, interpreted ) Ok, modules loaded: Main. A GHC telepítéséről a B. függelékben olvashatunk. Miután az állomány sikeresen betöltésre került, az értelmező lehetővé teszi számunkra, hogy egyenként hivatkozzunk az általunk definiált függvényekre, vagy akár kombináljuk ezeket. Az egész működését úgy kell elképzelünk, mint egy programozható számológépet, ahol kifejezéseket tudunk kiértékelni, és ehhez újabb és újabb függvényeket készíthetünk. A program a kiértékelendő kifejezéseket a sikeres betöltést követően egy Main*> kezdetű sorban, egy promptban várja. Itt maga a Main annak a függvénytárnak, modulnak a neve, amely a saját definícióinkat tartalmazza. Mivel nem adtunk neki külön nevet a forráskódban, az értelmező alapértelmezés szerint így nevezi el, függetlenül az állomány nevétől. A továbbiakban az értelmező promptját egyszerűen csak úgy jelöljük, hogy GHCi>. GHCi> negate 1 -1 GHCi> negate (negate 1) 1 GHCi> negate -1 :3:1: Non type-variable argument in the constraint: Num (a -> a) (Use FlexibleContexts to permit this) When checking that ‘it’ has the inferred type it :: forall a. (Num a, Num (a -> a)) => a -> a Ezt az értelmezővel folytatott párbeszédet Read-Eval-Print (mint beolvasni, kiértékelni, kiírni, röviden REP) ciklusnak hívják. Először az értelmező beolvassa és értelmezi a bemenetként kapott kifejezést, majd, amennyiben ez sikeres volt, kiértékeli, vagyis kiszámolja az eredményét, melyet végül kiír. Sajnos, ahogy a fenti példában látható, az utolsó kifejezés valamiért nem volt elfogadható. Ez arra mutat egy példát, amikor a fordító valamilyen oknál fogva nem képes megérteni a beolvasott szöveget, miközben az a nyelv helyesírási, másnéven szintaktikai szabályainak látszólag teljesen megfelel. A fordító ugyanis nem egyszerűen csak ezen szabályok szerint ellenőrzi a bemenetet, hanem elvégez egy ún. típusellenőrzési lépést is, amely tulajdonképpen 3
a kifejezés nyelvhelyességi, azaz szemantikai vizsgálatára utal. A konkrét hiba részleteit itt most nem fejtjük ki, röviden csak annyit jegyzünk meg, hogy mindez azért számít Haskellben szemantikai hibának, mert a - (mínusz) szimbólumot egyszerre lehet a kivonás bináris, és az előjelváltás unáris operátorának tekinteni. Ezért ez a megfogalmazás kisebb fejtörést tud okozni a fordító számára, így mint ökölszabály, mindig javasolt a programokban a negatív számokat külön zárójelbe tenni: GHCi> negate (-1) 1 Az értelmező használata során arra mindig ügyelnünk kell, hogy minden esetben, amikor a programot megváltoztatjuk, azt újra be kell töltenünk. Ezt az értelmezőn belül egy paranccsal tudjuk elvégezni, ennek a neve :reload. Figyeljük meg, hogy a parancs a : (kettőspont) szimbólummal kezdődik, ezzel tudja az értelmező megkülönböztetni a feldolgozandó kifejezéseket a parancsoktól. GHCi> :reload [1 of 1] Compiling Main Ok, modules loaded: Main.
( Tutorial.hs, interpreted )
A parancs rövidítéseként azt is írhatjuk, hogy :r, illetve maga a : (üres parancs) alkalmas arra, hogy az utolsóként kiadott parancsot megismételtessük. Érdemes tudni, hogy a :? segítségével az összes elérhető parancsot mindig lekérdezhetjük.
1.2. Elágazások függvényekben A függvénydefiníciók sokszor azonban nem ennyire egyszerűek, mivel alkalmanként el is kell ágazniuk. Például tegyük fel, hogy készíteni szeretnénk egy olyan függvényt, amelyik egy szám abszolút értékét képes kiszámítani. Ebben az esetben a szám értékétől függően, amennyiben az negatív, előjelet váltunk vagy változatlanul hagyjuk. Ez utóbbi kapcsolatban megjegyezzük, hogy a tisztán funkcionális programok esetében az értékek nem változhatnak meg a program futása során. Vagyis egy név mindig ugyanazt a hozzárendelt értéket hivatkozza, függetlenül attól, hogy a programban merre található. Ezt hivatkozási helyfüggetlenségnek nevezzük. Továbbá ehhez kapcsolódóan azt mondjuk, hogy a programbeli változóink egyszer kapnak csak értéket. Ennek megfelelően tehát a függvényünk majd nem fogja módosítani a kapott paraméter értékét, hanem helyette egy új, de már módosított értéket fog visszaadni. 4
Haskell programokban elágazásokat többek közt ún. őrfeltételek hozzáadásával képezhetünk. Az őrfeltételek olyan logikai értékű kifejezések, amelyeket a függvénydefiníció bal oldalán, a függvény nevét és a paraméterlistát követően helyezhetünk el a | (függőleges vonal) szimbólummal elválasztva. Ennek szemléltetéséhez most vegyük az osztási művelet egy olyan speciális változatát, ahol a számítást magát csak abban az esetben végezzük el, amikor az osztó nem egyenlő nullával: x ./. y | y /= 0 = x / y Ekkor a függvény törzsét (az egyenlet jobb oldalát) csak az őrfeltétel teljesülésekor fogja csak a program futtatását végző rendszer kiértékelni. Minden más esetben az adott törzs feldolgozása kimarad és a futtató rendszer folytatja a következő, teljesíthető őrfeltétellel rendelkező ágat, miközben fentről lefelé halad. Amennyiben nem adtuk meg további lehetséges törzseket, ún. függvényalternatívákat, futási idejű hiba, kivétel keletkezik. Ezt az értelmező közvetlenül meg is jeleníti, mivel ilyen esetekben nem képes választ adni a korábban feltett kérdésünkre: GHCi> 42 ./. 0 *** Exception: Tutorial.hs:5:3-26: Non-exhaustive patterns in function ./. Ezt a matematikából kiindulva parciális függvénynek nevezzük. Ezek olyan függvények, amelyek nem minden értékhez rendelnek másikat, bizonyos pontjaikban nem értelmezettek. Ahogy láthattuk, ezek alkalmazása viszont futási hibához vezet, amely egyúttal a teljes programunk kiértékelésének leállását jelenti. Ennek okán a gyakorlatban az ilyen függvények írása nem javasolt, a későbbiekben ennek elkerülésére látni is fogunk megoldásokat. A parciális függvény ellentéte a totális függvény, amely fogalmát szintén a matematikából kölcsönöztük, ahol minden értékhez rendelünk valamit. Most adjuk meg az abs, vagyis az abszolútérték-függvény definícióját őrfeltételek használatával! Vigyázzunk azonban a tördelésre! Ugyanis ez már egy többsoros definíció lesz, ahol a fordító a behúzások alapján képes megérteni, az egyes sorok miként kapcsolódnak egymáshoz. Ezt margószabálynak hívják, amelynek lényege, hogy a hosszabb definíciókat eltörhetjük és több sorban írhatjuk. Ilyenkor az első sor után következőket mindig bentebb kell húznunk szóközökkel, és ezáltal egy margót képzünk: abs x | x < 0 = negate x | otherwise = x
5
Ebben a definícióban tehát két eltérő ágat is felfedezhetünk. Az egyik fogalmazza meg a kivételes esetekre, vagyis a negatív számokra vonatkozó szabályt, és alkalmazza rájuk a korábban már definiált negate függvényünket. A másik pedig az összes többi esetet kezeli. Ez egyben egy olyan őrfeltételre is mutat példát, amely igazából nem akadályozza meg az adott törzs kiértékelését. Ebben ugyanis valójában az otherwise konstans szerepel, amely az azonosan igaz logikai értéket fedi: GHCi> otherwise True Az eddigiek alapján megfigyelhetjük, hogy az egyes alternatívák őrfeltételeit tehát a kiértékelés során fentről lefelé vizsgáljuk, és közülük végül azt a törzset választjuk, amely először értékelődik igazra. Vegyük észre, hogy ennek megfelelően, ha az otherwise feltétel szerepel először, akkor az minden más ágnál hamabb, tőlük lényegében függetlenül válik igazzá, így azok sosem fognak szóba kerülni. Ha viszont először a kivételeket soroljuk fel, képes az összes többi esetre választ adni, egyfajta védőhálóként megakadályozza, hogy a függvény véletlenül parciálissá váljon. Haskellben létezik továbbá az imperatív nyelvekben ismert if („ha . . . akkor . . .” utasítás) megfelelője is. Ez azonban, a nyelv és paradigma jellegéből fakadóan, nem utasítás, hanem függvény. A tisztán funkcionális nyelvekben ugyanis csak és kizárólag függvények vannak, nincsenek utasítások. Emiatt a programjaink sem lesznek többek, mint hatalmas kifejezések, amelynek egyszerűen csak ki akarjuk számítani az értékét. Másrészt ennélfogva már a legkisebb kifejezések is programnak számítanak, és az értelmező a kiértékeléssel ezeket a programokat futtatja. Ennek következményeképpen, bár az if kulcsszónak számít, teljesen egy háromparaméteres függvényként kell rá gondolnunk. Ezért mindig, minden paraméterét meg kell adnunk: az elágaztatás logikai feltételét, valamint az igaz és hamis értékeknek megfelelő kifejezések. GHCi> if True then 1 else 0 1 Ezen keresztül az abs függvény így lenne megadható az if használatával: abs’ x = if (x < 0) then (negate x) else x Azonban az ágak számának növekedésével az őrfeltételek sokkal jobb választásnak bizonyulnak, mivel így a programjaink rövidebbek maradnak. Ezért a funkcionális nyelvi programokban inkább ezeket szoktuk alkalmazni. 6
1.3. Programozás listákkal Az egész számok mellett Haskellben sok más típus is használható. Például, ahogy az otherwise esetében is láthattuk előzőleg, tudunk logikai értékekkel is dolgozni. Sőt, ahogy majd később (2. fejezet) láthatjuk, a nyelv tetszőleges típus definiálását lehetővé teszi. A funkcionális programokban másik gyakran előforduló típus a lista, amelynek történelme egészen az első funkcionális nyelvig, a LISP (mint "list processing") programozási nyelvig visszanyúlik. A listák értékek egyszerű tárolóiként használhatóak. A legegyszerűbb lista az üres lista. GHCi> [] [] De ennél bonyolultabb listákat is létre tudunk hozni az elemeik felsorolásával, vesszők között felsorolva: GHCi> [1,2,3,4,5] [1,2,3,4,5] Vagy akár magát az értelmezőt is megkérhetjük, hogy magától állítsa elő ugyanezt a listát. Ehhez mindössze a felsorolás alsó és felső korlátját kell megadnunk, köztük két ponttal: GHCi> [1..5] [1,2,3,4,5] Listákat nem csak így lehet építeni. Ezeket valójában az előbb bemutatott üres lista és egy ún. építő operátor segítségével lehet készíteni, amelynek jele a : (kettőspont). A : operátornak egy listaelemre és listára van szüksége, melyekből képes egy újabb listát készíteni. Ez egy jobbasszociatív művelet, vagyis ha többször egymásba ágyazva alkalmazzuk, akkor mindig a jobb oldali példányt kell először kiértékelni. GHCi> 1 : (2 : (3 : (4 : (5 : [])))) [1,2,3,4,5] Érdemes tudni, hogy az egyszerűség kedvéért a fordító mindig ebben a formában tárolja a listákat. Az imént bemutatott többi lehetőség csupán ennek egy-egy másik felírási módja, amely a könnyebb olvashatóságot hívatott elősegíteni. Ezt nyelvi ízesítésnek szoktuk nevezni, amely egy gyakran alkalmazott technika a funkcionális nyelvek definíciójában. 7
A listák eredeti ábrázolási módjával azért is fontos tisztában lennünk, mert így listákat feldolgozó függvényeket is lehetőségünk nyílik írni. Erre példaként tekintsünk egy olyan függvényt, amely az == operátor (egyenlőségvizsgálat) segítségével ellenőrzi, hogy egy adott lista üres vagy sem: isEmpty xs = xs == [] amelyet a következőképpen próbálhatunk ki az értelmezőben: GHCi> isEmpty [] True GHCi> isEmpty [1..5] False Megjegyezzük, hogy ilyen függvényeket lehetőségünk van egy másik eszközzel, ún. mintaillesztéssel megfogalmazni. A mintaillesztés során a függvény által kapott értéket annak szerkezete szerint különböző mintákkal vetjük össze és annak alapján választjuk meg a függvény eredményét. Ezen keresztül, az őrfeltételek használatához hasonlóan, függvényalternatívák sorozatát tudjuk felsorolni, melyek mindegyikéhez egy-egy minta fog tartozni. A függvény értékének kiszámítása során ezeket a mintákat fogjuk azok megadásának sorrendjében (fentről lefelé) megpróbálni illeszteni a függvény paramétereire, és a kiértékelést azzal a függvénytörzssel folytatjuk, ahol azok a szerkezeti szabályok szerint megfelelnek. Az összes többi törzs ekkor feldolgozatlan marad. Például annak eldöntése, hogy egy lista üres vagy sem, ezzel a módszerrel a következő módon fogalmazható meg: null [] = True null _ = False Itt az első alternatíva csak és kizárólag az üres lista konstans esetén fog illeszkedni, és ekkor a függvény a True (igaz) értéket veszi fel. Az összes többi lehetőséget egy ún. joker mintával fedjük le, amely tetszőleges értékre illeszkedik. Ennek kapcsán hozzátesszük, hogy a joker minta alkalmazásakor az adott paraméter értékehez sem tudunk hozzáférni (hiszen nem neveztük el), ezért ilyet akkor írunk, ha attól függetlenül akarjuk képezni a függvény értékét. Emiatt a joker mintát úgy is nevezhetjük, hogy névtelen változó. Ennél összetettebb listákat úgy tudunk feldolgozni függvényekkel, ha a listák felépítésének inverzében gondolkodunk. Vagyis a : szimbólummal most nem egy elemet és egy listát építünk össze listává, hanem egy listát bontunk fel ennek segítségével egy elemre és egy listára. Ezeket, a szintén LISP-től 8
származó örökség részeként, a lista fejének és törzsének nevezzük. A nekik megfelelő függvények már csak mintaillesztés segítségével fogalmazhatóak meg: head (x:_) = x head _ = error "head: empty list" tail (_:xs) = xs tail _ = error "tail: empty list" Innen talán jobban kiderül, hogy a mintaillesztés valójában kicsivel több, mint mezei egyenlőségvizsgálat. Észrevehetjük ugyanis, hogy egy minta tartalmazhat lyukakat, amelyeket változónevekkel tudunk lefedni. Az illesztés során ezeket a lyukakat fogjuk majd kitölteni az adott paraméter mintának megfelelő, egyező részeivel, melyekre aztán így később a függvény törzsében akár külön-külön is hivatkozni tudunk. Mellette azt is megfigyelhetük, hogy a listákra vonatkozó mintákat zárójelbe kellett tennünk, mivel ott egyetlen értéket akarunk több részre felbontani. A head definíciójában egy lista csak akkor fog illeszkedni az első alternatívához tartozó mintára, amennyiben azt annak idején a : szimbólummal hoztuk létre. Minden más esetben egy hibaüzenetet hozunk létre, amely lényegében a [], azaz az üres lista esete. Erre azért van szükség, mert ha az üres listának nincs feje, vagyis nem tudunk belőle elölről leválasztani elemet. Így a head emiatt egy parciális függvény lesz. Ugyanez a gondolatmenet érvényes a tail esetében is. GHCi> head [] *** Exception: head: empty list GHCi> head [1..5] 1 GHCi> tail [1..5] [2,3,4,5]
1.4. A rekurzió A listák esetében gyakorta előfordul, hogy a függvénnyel a teljes listát végig kell járnunk. Például elegendő csak arra gondolnunk, amikor el akarjuk dönteni, hogy két lista egyenlő-e. Ilyenkor, mivel nem tudjuk pontosan a program írásakor, az egyes listák milyen hosszúak lehetnek, valamilyen, az egyes elemek esetében azonos módon elvégezhető, általánosított lépéssorozat ismétlésére, iterálására van szükségünk. 9
Funkcionális nyelvekben erre a rekurzió fogalmát használják fel. Egy függvényt rekurzívnak nevezünk minden olyan esetben, amikor a definíciójában saját magára hivatkozik. Ezért gyakran a rekurziót úgy is szokták tréfásan definiálni, hogy „Rekurzió: ld. rekurzió.” A tisztán funkcionális nyelvekben nagyon óvatosan kell bánnunk az imperatív nyelvekből ismert, teljesen ártatlan megoldásokkal, mint amilyen a következő is: x = x + 1 Ha imperatív módon tekintünk a fenti egyenletre, akkor ezt úgy kellene értelmeznük, mint az x értékének növelését eggyel. Ez viszont a Haskell működési elvei szerint egy végtelen rekurzió eredményez, amely kiértékelése során az értelmező sosem lesz képes befejezni az eredmény meghatározását. Ez azért történik így, mert ebben az esetben definiálni akarjuk az x függvényt, amely tulajdonképpen egy konstans (mivel nincs paramétere, tehát mindig ugyanazt az értéket fogja képviselni), és ennek meghatározásához szükségünk lenne annak korábbi értékére. Ezt az értéket viszont éppen akkor szeretnénk kiszámítani, amely utána folyamatosan, a végtelenségig magára hivatkozik. Az imperatív nyelvekben ez a szerkezet azért működőképes, mert az x értékének van egy állapota, és amikor a fenti értékadást értelmezzük, akkor annak bal oldalán mindig az új, a jobb oldalán pedig a régi állapotáról beszélünk. Tisztán funkcionális nyelvekben azonban a hivatkozási helyfüggetlenség miatt végig ugyanarról értékről beszélünk, innen adódik az eltérő viselkedés. Ha valamiért egy ilyen végtelen ciklusba keverednénk a számítások során, a Ctrl+C billentyűkombinációval ezeket bármikor megszakíthatjuk: GHCi> x ^CInterrupted. Ennek ellenére, meglepő módon, Haskellben az ilyen végtelen eredményt gyártó függvények esetenként lehetnek hasznosak, mindössze csak a megfelelő típusban kell gondolkodnunk. Például tekintsünk az alábbi függvény definícióját: repeat x = x : (repeat x) Ezt a következő módon tudjuk használni az értelmezőn keresztül: GHCi> repeat 1 [1,1,1,1,1,1,1,1,1,1,1^CInterrupted. 10
Habár láthattuk, hogy a függvény kiszámítása ebben az esetben sem fog önmagától befejeződni, az értelmező mégis képes volt valamilyen köztes eredményt, egyesek véget nem érő folyamát, megjeleníteni. Ennek megértéséhez észre kell vennünk, hogy a repeat függvény definícióját nem feltétlenül úgy kell olvasnunk, ahogy azt az imperatív nyelvek esetében megszokhattuk. Annak megfelelően elsőként ugyanis a zárójeles részt, a repeat x részkifejezést kellene kiszámítanunk, és ehhez kellene a : alkalmazásán keresztül az x értékéből még egy elemet az így elkészített lista elé fűzni. Ezt a kiértélési módszert mohónak nevezzük, ahol a függvények alkalmazásához először mindig ki akarjuk számítani a paraméterek értékeit, és csak utána velük a függvény értékét. Azonban létezik egy másik megközelítési mód, ahol elsőként mindig a függvényt számítjuk ki, és a paramétereivel kizárólag csak akkor foglalkozunk, amennyiben arra szükségünk van. Emiatt elképzelhető az is, hogy egyáltalán nem fogjuk valamelyik paramétert kiértékelni. Ezt lusta kiértékelésnek nevezzük, és Haskellben is ezt alkalmazzák. Ennek megfelelően a repeat értékének kiszámítása során először a felsőbb szinten szereplő operátort, vagyis a : műveletét végezzük el először, és így a még el nem készült lista elejére illesztjük vele az x értékét. Ezt folytatjuk a repeat rekurzív kiszámításával, amellyel mögé kerül egy másik x érték, és az egész folyamat egészen a végtelenségig halad. A lustaságnak és annak köszönhetően, hogy a részkifejezéseket így csak akkor értékeljük ki, amennyiben ténylegesen szükségünk van az értékükre, az alábbi kifejezés viszont már véges idő alatt kiszámítható lesz: GHCi> head (repeat 1) 1 A kapott eredmény fenti gondolatmenetet követve teljesen logikusnak tűnik: miért bontanánk ki a teljes listát, miközben a válaszadáshoz elegendő csak az első elemének meghatározása? A lustaságnak köszönhetően Haskellben lehetőségünk van végtelen adatszerkezetekkel dolgozni, amely az algoritmusok leírását is meglepően elegánssá és tömörré tudja tenni. Fontos megjegyeznünk, hogy nem minden funkcionális nyelv esetében igaz, mivel a mohó kiértékelés azokban is sokáig az uralkodó kiértékelési stratégia volt, tehát például a LISP is ilyen. Természetesen a repeat függvény a véges változatát is el tudjuk készíteni, ha korlátozzuk a listába illeszthető elemek számát. Tisztán funkcionális programozás esetében, mivel nincsenek állapottal rendelkező nevek, vagyis a hagyományos értelemben vett programváltozók, ezt úgy tudjuk megoldani, ha felveszük a függvénynek egy újabb paramétert. Ez a paraméter egy 11
számláló szerepét fogja játszani, amelyet a korlát adott értékétől visszafele indulva lépésenkét mindig eggyel csökkentünk egészen addig, amíg az pozitív. Így lényegében két esetet fogunk kapni. Egy ún. induktív esetet, amikor a rekurzív hivatkozással megadjuk, hogy miként építjük a listát, miközben csökkentjük a számlálót, és egy ún. alapesetet, amikor a függvény rekurzió segítsége nélkül képes lesz közvetlenül meghatározni az értékét. Az induktív eset felel meg a ciklus lépéseinek, magjának újbóli végrehajtásának, az alapeset pedig a ciklusból kilépés, vagyis az ismétlés megállításának feltételeit írja le. Ezeket az eseteket függvényalternatívák felhasználásával adhatjuk meg. Így a repeat véges változata, a replicate a következőképpen áll elő: replicate n x | n <= 0 = [] | otherwise = x : (replicate (n - 1) x) Megfigyelhető, hogy a replicate első paramétere, vagyis a számláló, rekurzívan mindig az előzőnél eggyel kisebb értékkel hívódik meg. Ellenkező esetben a rekurzió sosem fejeződne be. Ezért fontos törekednünk arra, hogy az induktív esetek megfogalmazása során mindig igyekezzünk elérni az alapesetekben leírt leállási feltételeket. Ezt úgy tehetjük meg, hogy a rekurzív hívás során legalább az egyik paramétert megváltoztatjuk. Ez a replicate tehát esetében azt jelenti, hogy a számláló értéke lépésenként csökkent és az ismétlés megáll, amikor nullára vagy az alá érünk. GHCi> replicate 0 1 [] GHCi> replicate 3 1 [1,1,1] GHCi> replicate (-3) 1 [] Nem csak számok, de más típusú értékek is csökkenthetőek, ezáltal rekurzív stílusban feldolgozhatóak. Ilyenek többek között a listák, ahol csupán a lista törzsének a továbbadása elegendő lehet egy alapeset eléréséhez, amely ekkor általában az üres lista. Emiatt listák esetében a törzs kiszámítása lényegében az eggyel csökkentésnek, az üres lista pedig a nulla konstansnak feleltethető meg. Mindezekre példaként tekintsünk most a take függvény definícióját, amelynek az a feladata, hogy egy lista elejéről adott számú elemet adjon vissza, amennyiben ez lehetséges. Ha nem, akkor adja vissza az eredeti listát változatlanul. 12
take _ [] = [] take n _ | n <= 0 = [] take n (x:xs) = x : take (n - 1) xs Észrevehetjük, hogy ebben a definícióban mintaillesztést és őrfeltételeket is alkalmaztunk vegyesen, így fejeztünk ki két lehetséges alapesetet. Az első sor értelmében ha a feldolgozandó lista üres, akkor az első paraméter (a számláló) értékétől függetlenül egyszerűen csak adjunk vissza egy üres listát. A második sor szerint ha a kivenni kívánt elemek számát jelző számláló már nem pozitív, akkor ismét adjunk vissza üres listát, hiszen már nem kell belőle többet kivennünk. Végezetül a harmadik sorban azt olvashatjuk, hogy minden más esetben vegyük a lista első elemét és illesszük hozzá a : operátorral ahhoz a listához, amelyet úgy nyerünk, hogy egy eggyel rövidebben listából veszünk ki, a take rekurzív alkalmazásával, eggyel kevesebb elemet. Ehhez az esethez a mintaillesztés és az őrfeltételek viselkedésének megfelelően mindig akkor jutunk, ha az előtte szereplő alapesetek feltételei közül egyik sem teljesült még. A take függvény is lusta lesz, így képes akár végtelen listákkal is dolgozni. Például olyanokkal, amelyeket a repeat felhasználásával állítottunk korábban elő: GHCi> take 3 (repeat 1) [1,1,1] Ennek mikéntjének pontosabb megértéséhez tekintsük át, miként is fog az adott kifejezés kiértékelése végbemenni: take 3 (repeat 1) ----------------< illeszkedés a take 3. sorára, ahol n = 3, x = 1, xs = repeat 1 > 1 : take (3 - 1) (repeat 1) 1 : take 2 (repeat 1) ----------------< illeszkedés a take 3. sorára, ahol n = 2, x = 1, xs = repeat 1 > 1 : 1 : take (2 - 1) (repeat 1) 1 : 1 : take 1 (repeat 1) ----------------< illeszkedés a take 3. sorára, ahol n = 1, x = 1, xs = repeat 1 > 1 : 1 : 1 : take (1 - 1) (repeat 1) 1 : 1 : 1 : take 0 (repeat 1) ----------------13
< illeszkedés a take 2. sorára, ahol n = 0 > 1 : 1 : 1 : [] [1,1,1] Emellett még az is tetten érhető, hogy a replicate tulajdonképpen a take és a repeat kompozíciójaként is megfogalmazható, amely remekül összeegyeztethető a moduláris programozás elveivel: replicate’ n x = take n (repeat x)
1.5. Rekurzió listák felett: hajtogatás A listák felett szervezett rekurzió kapcsán érdemes foglalkozni valamennyit a mögötte megbúvó sémával. Ez egy jól általánosítható séma, amelyet hajtogatásnak nevezzük. Ez arról szól, hogy folyamatosan vesszük egy lista elemeit és belőlük egy kétparaméteres függvény felhasználásával lépésenként egy görgetett, hajtogatott értéket építünk fel, amely aztán az így képzett számítás végeredménye lesz. Az elemek bejárásának, így a hajtogatásnak az iránya lehet balról jobbra: (. . . ((((z ⊕ x0 ) ⊕ x1 ) ⊕ x2 ) ⊕ x3 ) ⊕ . . .) ⊕ xn vagy jobbról balra: x0 ⊕ (x1 ⊕ (x2 ⊕ (x3 ⊕ (. . . (xn ⊕ z) . . .)))) ahol ⊕ a kétparaméteres függvény, az x0 , x1 , . . ., xn értékek a összehajtogatni kívánt lista adott indexű elemei, valamint a z a hajtogatás során képzett, göngyölt eredmény kezdőértéke. A ⊕ függvénynek attól függően, hogy balról vagy jobbra hajtogatunk vele, bal- illetve jobbasszociatívnak kell lennie. Értelemszerűen asszociatív függvények mind a két esetben alkalmazhatóak. Például tekintsük az elemek összeadását! Ekkor az ⊕ operátor az összeadás (+) lesz, a hozzá tartozó kezdőérték a 0, és a hajtogatás során kiszámított érték pedig a listában szereplő elemek összege. Annak alapján, amit eddig láthattunk a listák felett értelmezett rekurzióról, nem is annyira nehéz megadni egy ilyen függvény definícióját: sum [] = 0 sum (x:xs) = x + sum xs Ha az egyes szabályokat valamilyen lista esetében értelmezni kezdjük, akkor láthatjuk, hogy a függvény alkalmazásával a következő transzformációt végezzük el: 14
sum [1,2,3] --> 1 + sum [2,3] --> 1 + (2 + sum [3]) --> 1 + (2 + (3 + sum [])) --> 1 + (2 + (3 + 0)) A funkcionális programozásban ez a séma megfogható egy alkalmas függvényfajtával, amelyet magasabbrendű függvényeknek nevezünk. Magasabbrendűnek nevezünk minden olyan függvényt, amely vagy függvényt kap paraméterül, vagy pedig függvényt hoz létre eredményként. Ez a lehetőség abból származik, hogy funkcionális nyelveken a függvények az értékekhez, például számokhoz hasonlóan feldolgozhatóak és képezhetőek. Itt és most csak az első esetet használjuk ki, vagyis amikor a függvényünk egy másik függvényt kap paraméterül, de később majd kitérünk a másik esetből következő lehetőségekre is. Kezdésképpen azonban még ne az imént megismert sémát próbáljuk meg ezen a módon kifejezni, hanem helyette tekintsünk egy egyszerű, de érdekes példát a magasabbrendű függvényekre, a map függvényt. Ez a függvény egy függvényt és egy listát kap paraméterül, majd visszaad egy olyan listát, ahol a lista összes elemére alkalmazza a függvényt. Az angol matematikai szaknyelvben ugyanis a "map" „leképezést” jelent, vagyis amikor vesszük egy halmaz összes elemét, és azt teljes egészében egy másik halmazba képezzük át. GHCi> map negate [1,-1,2,-2,3,-3] [-1,1,-2,2,-3,3] Megfigyelhetjük, hogy a negate függvényt látszólag mindenféle paraméter nélkül hívtuk meg. Ez annak a következménye, hogy a függvényt értékként fogtuk meg, és ilyenkor csak a nevére van szükségünk. Minden mást meg fog kapni a map függvénytől, ahogy annak a definíciójából is kiderül: map _ [] = [] map f (x:xs) = (f x) : (map f xs) Látható tehát, hogy a negate itt az f paraméter értékeként jelenik, és a definícióban ennek adjuk át folyamatosan a listában egymás után kivett értékeket. A függvényt egyszerűen csak a map egyik paramétereként vettük fel és úgy használjuk, mintha egy korábban már definiált függvényről lenne szó.
15
1.6. Függvények függvényei Most, miután láttuk, hogy miként lehet rekurzív és magasabbrendű függvényeket készíteni, fogalmazzuk meg a korábban említett hajtogatási sémát! Az egyszerűség kedvéért itt csak a jobbról hajtogatással, vagyis a foldr ("fold right") függvény definíciójával foglalkozunk, de ehhez hasonlóan a balra hajtogatás, vagyis a foldl ("fold left") is megadható: foldr _ z [] = z foldr f z (x:xs) = f x (foldr f z xs) Tekintsük a definíció egyes részeit! Amikor a lista üres, a függvény értéke legyen a hajtogatás eredményének kezdőértéke, mivel ebben az esetben befejeződik a rekurzió. A listában tárolt számok összegzésénél ez lényegében azt jelentette, hogy az üres listához az összeadás egységelemét, a nullát rendeltük. Amennyiben a lista nem üres, vegyük a lista soron következő, vagyis első elemét és a függvény felhasználásával azt kombináljuk össze azzal az értékkel, amelyet úgy nyertünk, hogy a lista fennmaradó részére (törzsére) alkalmaztuk a hajtogatást (jobbasszociatív) módon. Ezzel a sémával most már képesek vagyunk a sum függvényt akár egyetlen sorban összefoglalhatóan leírni: sum xs = foldr (+) 0 xs Itt láthatjuk, hogy a számok összegzéséhez a + függvényt és a 0 kezdőértéket adtuk át a foldr függvénynek. Nem nehéz ellenőrizni, hogy ha ezeket a paramétereket közvetlenül behelyettesítjük a foldr definíciójába, akkor visszakapjuk belőle a sum definícióját. Ezért is tekinthetőek a magasabbrendű függvények a hagyományos függvényeknél erősebbeknek: az általuk megfogalmazott függvényosztályban minden függvény kifejezhetően csupán annyival, hogy a megfelelő törzset helyettesítjük a definíciójukba. A fenti példában a + műveletet ismét paraméterek nélkül adtuk át. Illetve, mivel operátor, és ezért a nyelv helyesírási szabályai szerint szimbólumokból kell, hogy álljon, zárójelbe is kellett tennünk. Természetesen a foldr függvénynek bármilyen más függvény is átadható, akár olyanok is, amelyeket mi magunk írtunk. Velük szemben az egyedüli igazi követelmény, hogy a típusuk megfelelő legyen. Noha a típusok kérdéskörét eddig ügyesen sikerült elkerülnünk, tagadhatatlan, hogy a Haskell programok írásának ez egy másik létfontosságú, azonban sokszor láthatatlan része. Haskellben minden függvénynek van típusa annak ellenére, hogy ezek közül eddig egyetlen egyet sem említettünk. Az értelmezőben az egyes kifejezések típusát a :type (vagy röviden :t) paranccsal kérdezhetjük le. Nézzük meg például meg, hogy mi a foldr típusa: 16
GHCi> :type foldr foldr :: (a -> b -> b) -> b -> [a] -> b A válasz megértéséhez elsőként megjegyezzük, hogy Haskellben a nevekhez a típusra vonatkozó információt a :: (dupla kettőspont) szimbólummal kapcsoljuk. Továbbá a függvények típusaiban a -> (nyíl) szimbólum szerepel, amely lényegében egy típusok felett értelmezett operátor, amelyet arra használunk, hogy leírjuk vele a függvény értelmezési tartománya és annak értékkészlete közötti összefüggést: f :: A -> B Ekkor tehát az f egy olyan függvény lesz, amelyik az A típusból (mint értelmezési tartományból) a B típusba (mint értékkészletbe) képez. Többparaméteres függvények esetében alkalmazhatnánk a matematikában megszokott jelölést, vagyis az értelmezési tartományok Descartes-szorzatát. Például úgy, hogy a létezik egy másik típusszintű operátor, az x, amely két típus szorzatát írja le: f :: A x B -> C Ilyen lehetőség létezik Haskellben is, azonban ezt a , (vessző) operátorral jelöljük: f :: (A , B) -> C Azonban technikai okból, melyekről majd a későbbiekben lesz részletesebben szó, a nyelv tervezői ehelyett mindenhol csak a nyíl operátor alkalmazása mellett döntöttek: f :: A -> B -> C Ezáltal a függvények típusát a következő ökölszabály szerint lehet könnyen értelmezni. A nyilakkal elválasztott részek közül az első (n − 1) darab tag a rendre paraméterek típusainak feleltethető meg, míg az utolsó, vagyis n. tag a függvény értékének típusát adja meg. Ennek a magyarázatnak megfelelően kiderül, hogy a foldr függvénynek három paramétere van: – a -> b -> b – b – [a] 17
Itt a függvények típusa mellett egy másik típusoperátort is felfedezhetünk, ez a [] avagy a lista szimbóluma. Ez szintén egy típusok felett értelmezett függvény, azonban ennek csak egyetlen paramétere van, a listában szereplő elemek típusa. Ez tehát, hasonlóan a -> viselkedéséhez, egy típusból egy másik típust képez, az adott típusú elemeket tartalmazó lista típusát. A rövid alapozás után most menjünk egyesével végig a foldr paraméterein: az első egy függvény, a második valamilyen érték, a harmadik pedig egy lista. Ami azonban feltűnő lehet, hogy nem látunk bennük egyetlen konkrét típust sem, helyettük csak az a és b betűk szerepelnek. Ezek a típusokban szereplő változók, vagyis típusváltozók, amelyeken keresztül az ún. parametrikus polimorfizmus jelenik meg. Ez az jelenti, hogy a foldr függvény nem csak adott típusokra alkalmazható, hanem automatikusan képes szinte tetszőleges típusú értékekkel dolgozni. A változókat arra használjuk a típus leírásában, hogy az egyes paraméterek, illetve a visszatérési érték egymáshoz való logikai viszonyait kifejezzük. Így, ha ezeket a típusváltozókat tényleges típusokkal helyettesítjük, ennek az egyébként absztrakt típusnak kapjuk meg végtelen sok konkretizált változatát. Például tekintsük azt az esetet, amikor az a értéke Integer, a b értéke pedig Bool, ahol az Integer egész számot, a Bool logikai értéket jelent: foldr :: (Integer -> Bool -> Bool) -> Bool -> [Integer] -> Bool Azonban a helyettesítéskkel kapcsolatban van egy nagyon fontos szabály. Az egyes típusváltozók értékét mindig csak ugyanarra a típusra cserélhetjük. Tehát a foldr alábbi konkretizálása helytelen, ezzel a paraméterezéssel már nem használható: foldr :: (Bool -> Bool -> Bool) -> Integer -> [Integer] -> Integer Az eddigi függvényeink típusát ún. típuskikövetkeztetésen keresztül kaptuk meg, ezért nem volt szükséges nekünk kitalálni és megadni. A típuskikövetkeztetés egy algoritmus, amely mindig megpróbálja a függvény legáltalánosabb, vagy más néven principális típusát meghatározni. A foldr esetében az imént megadott, típusváltozókat tartalmazó típus az összes lehetséges közül a legáltalánosabb, mivel a függvény leírása során: – Mivel a függvény harmadik paraméterére egyszer az üres listát ([]), máskor pedig az : szimbólumon keresztül a listák felbontását lehetővé tevő mintát illesztettük, feltételezhető, hogy ez valamilyen értékeket tartalmazó, vagyis egy a típusú lista.
18
– A második paraméterrel nem csináltunk semmi különlegeset, ezért nem lehetünk biztosak benne, hogy a listákban található értékek típusával azonos típusú lesz, így egy új, eddig nem használt típusváltozót rendelünk hozzá, ez legyen a b. – Végezetül, az első paramétert úgy használtuk, mint egy függvényt, amely a listából kivett (a típusú) elemet kapja első paramétereként, majd a a foldr rekurzív hívásával számolt (b típusú) értéket második parmétereként és ugyanolyan típusút is ad vissza, annak típusának végül annak kell lennie, hogy a -> b -> b. Ez utóbbira bizonyítékot a függvény definíciójának első sorában láthatunk, amikor a második paramétert változtatás nélkül visszaadjuk, amelyről már tudjuk, hogy b típusú. Amikor a fordító nem képes ez egy ehhoz hasonló gondolatmenettel magától kikövetkeztetni a típust, hibát jelez és nem fordítja le a programunkat. Ezért ezt a folyamatot típusellenőrzésnek is nevezik. A típusok kikövetkeztetése nem csak a típusokra vonatkozó információk megadásától mentesít minket, hanem arra is alkalmas, hogy ellenőrizzük az adott definíció értelmét. Tehát ez lényegében a programunk egyfajta szemantikai értelmezéseként is szolgál. Képzeljük el a foldr definíciójának egy látszólag helyes, viszont valójában egy elrontott változatát: foldr _ z [] = z foldr f z (x:xs) = f x (foldr z f xs) Ha ezt a programot most be akarnánk tölteni az értelmezőbe, akkor válaszul egy típusra vonatkozó hibaüzenetet fogunk kapni, amely tájékoztat arról, hogy nincs minden rendben: GHCi> :load Fail.hs [1 of 1] Compiling Main
( Fail.hs, interpreted )
Fail.hs:4:33: Occurs check: cannot construct the infinite type: t1 ~ t -> t1 -> t1 Relevant bindings include xs :: [t] (bound at Fail.hs:4:14) x :: t (bound at Fail.hs:4:12) z :: t1 (bound at Fail.hs:4:9) f :: t -> t1 -> t1 (bound at Fail.hs:4:7) 19
foldr :: (t -> t1 -> t1) -> t1 -> [t] -> t1 (bound at Fail.hs:3:1) In the first argument of ‘foldr’, namely ‘z’ In the second argument of ‘f’, namely ‘(foldr z f xs)’ Failed, modules loaded: none. Ehhez azonban érdemes hozzátenni, a foldr több különböző változata lehet típusosan helyes annak ellenére, hogy nem felel a fentebb megfogalmazott specifikációnknak. Ezért, bár a típusleírást nem minden esetben kötelező megadnunk, jó programozási gyakorlatnak számít, ha a fontosabb függvények definíciójának részeként annak típusát is megadjuk. Ez segít többek között észrevenni, ha a függvény típusa véletlenül idő közben mégis megváltozna. Például az utolsó sorban az x és f változókat felcseréljük: foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ z [] = z foldr f z (x:xs) = x f (foldr f z xs) Ez explicit típusdeklarációnak köszönhetően azonban a fordító képes rámutatni erre a figyelmetlenségre: [1 of 1] Compiling Main
( Fail.hs, interpreted )
Fail.hs:5:20: Couldn’t match expected type ‘(a -> b -> b) -> b with actual type ‘a’ ‘a’ is a rigid type variable bound by the type signature for foldr :: (a -> b -> at Fail.hs:3:10 Relevant bindings include xs :: [a] (bound at Fail.hs:5:14) x :: a (bound at Fail.hs:5:12) z :: b (bound at Fail.hs:5:9) f :: a -> b -> b (bound at Fail.hs:5:7) foldr :: (a -> b -> b) -> b -> [a] -> b (bound The function ‘x’ is applied to two arguments, but its type ‘a’ has none In the expression: x f (foldr f z xs) In an equation for ‘foldr’: foldr f z (x : xs) = Failed, modules loaded: none.
20
-> b’
b) -> b -> [a] -> b
at Fail.hs:4:1)
x f (foldr f z xs)
1.7. Részlegesen alkalmazott függvények Ha visszaemlékszünk, volt egy másik magasabbrendű függvényünk is, a map. Ennek a típusát is le lehet kérdezni: GHCi> :type map map :: (a -> b) -> [a] -> [b] A definíció alapján a korábban informálisan bemutatott gondolkodásmód alapján a foldr függvényhez hasonlóan ennek a legáltalánosabb típusa is kikövetkeztethető. Amikor viszont a példában a negate függvénnyel használtuk, a típusban szereplő (a és b) típusváltozókat az Integer típusra szűkítettük: GHCi> map negate [1,-1,2,-2,3,-3] [-1,1,-2,2,-3,3] Azonban érdemes megjegyezni, hogy a map függvénynek nem csak egyparaméteres függvényeket tudunk átadni. Haskellben, mivel a többparaméteres függvények értelmezési tartományait nem Descartes-szorzatokkal ábrázoljuk, lehetőségünk nyílik arra, hogy a függvényeket részlegesen, vagyis az eredeti paraméterszámánál kevesebb paraméterrel alkalmazzuk. Ennek megértéséhez tekintsük a const függvény definícióját: const :: a -> b -> a const x _ = x Ez a függvény két paramétert vár, amelyek közül csak az elsőt adja vissza. GHCi> const 1 2 1 GHCi> const True False True Ahogy eddig is láthattuk a (szöveges névvel rendelkező) függvények esetében, az alkalmazásukhoz előre a függvény nevét írjuk, majd az után szóközökkel elválasztva felsoroljuk a paramétereit. Most viszont hozzátesszük, hogy a függvényalkalmazás valójában egy balasszociatív bináris operátor, maga a szóköz, egyik oldalán a függvénnyel, másik oldalán annak paraméterével. Ezt láthatóvá tudjuk tenni úgy, ha az előbbi kifejezésben az összes függvényalkalmazást bezárójelezünk:
21
GHCi> ((const True) False) True Mindemellett a const True kifejezés típusát is le tudjuk kérdezni: GHCi> :type const True const True :: b -> Bool Ebből kiderül, hogy az egyik paraméter elhagyásával egyszerűen létrehoztunk egy másik függvényt. Ez egyben meg tudja magyarázni, hogy a nyelv kialakításakor miért így kezdték el ábrázolni a függvényeket. Megjegyezzük, ennek következményeként a -> típusoperátor jobbasszociatív lesz, így a const típusa a következőképpen lesz leírható: const :: a -> (b -> a) Ez a tulajdonság hasznosnak tud bizonyulni a magasabbrendű függvények alkalmazása során is. Vegyük például a map függvényt, ahol az első paraméternek a const függvény is megadható, amennyiben annak első paraméterét rögzítjük a korábbi módon: GHCi> map (const True) [1..5] [True,True,True,True,True] Ekkor a listában szereplő számok egyike sem megjelenni az eredményként keletkező listában, egyedül a True konstans fog egymás után a számuknak, vagyis a lista hosszának megfelelően ismétlődni.
1.8. Típusok Minden, eddig szerepelt függvénynek természetesen ugyanúgy van típusa, például a negate esetében: negate x = 0 - x a típusa a következő: GHCi> :type negate negate :: Num a => a -> a
22
Ez szinte teljesen tud illeszkedni ahhoz a naiv sejtésünkhöz, mely szerint ez egy egyparaméteres függvény, amely a paraméterével azonos típusú értéket hoz létre. Egyedüli eltérés ettől a típusban a Num a => előtag megjelenése. Ezt a típusváltozóra vonatkozó megszorításnak vagy röviden csak megszorításnak hívják, és a - operátor alkalmazásából kaptuk: GHCi> :type (-) (-) :: Num a => a -> a -> a Azt már tudhatjuk, hogy a típusváltozók jelenléte polimorf függvényekre utal. Ezért azt mondhatjuk, hogy a - több különböző típusú értékre is felhasználható. A típusváltozók általában tetszőleges Haskellbeli típusra kicserélhetőek. Viszont ha a típus leírásához rájuk vonatkozóan egy megszorítás is megjelenik, akkor azzal a behelyettesíthető típusokat lényegében leszűkítjük egy adott csoport elemeire. A Num is egy ilyen csoport, pontosabban osztály, amely azon típusok osztályát jelenti, amelyek számokat ábrázolnak. Haskellben ilyen típusok például az Integer vagy Double, így a - művelet mind a két esetben alkalmazható, miközben az adott típusra jellemző változatot használjuk a háttérben. Ez úgy is felfogható, mint a függvénynevek túlterhelése, amikor ugyanaz a név több típus esetén is újrahasznosítható. Vagy megfordítva, ugyanaz a függvény a típustól függően többféleképpen képes viselkedni. Ezt eseti, vagy „ad hoc” polimorfizmusnak szokták nevezni. GHCi> GHCi> -1.0 GHCi> GHCi> -1
De a Num osztály nem csak a - operátort tartalmazza, hanem benne megtalálható minden, számokkal kapcsolatos általános művelet. Erről bővebb tájékoztatást az értelmezőn keresztül az :info vagy röviden :i paranccsal kérhetünk: GHCi> :info Num class Num a where (+) :: a -> a -> a (-) :: a -> a -> a (*) :: a -> a -> a negate :: a -> a 23
abs :: a -> a signum :: a -> a fromInteger :: Integer -> a -- Defined in ‘GHC.Num’ instance Num Word -- Defined in ‘GHC.Num’ instance Num Integer -- Defined in ‘GHC.Num’ instance Num Int -- Defined in ‘GHC.Num’ instance Num Float -- Defined in ‘GHC.Float’ instance Num Double -- Defined in ‘GHC.Float’ A class kulcsszó egy ilyen típusosztályt vezet be, amely után annak neve szerepel, ebben az esetben a Num, majd egy típusváltozó. Ezt a változót tudjuk az osztály leírásában arra használni, hogy megadjuk az összes olyan függvényt, amelynek rendelkeznie kell valamilyen definícióval az összes olyan típus esetében, amelyek ennek az osztálynak az elemei. A típusosztályokat ún. példányok megadásával a forráskód bármelyik részén bővíthetjük. Ehhez mindössze annyit kell tennünk, hogy az instance kulcsszóval bevezetve megadjuk az osztály nevét és a típusváltozó helyére kitöltjük azt a típust, amelyre vonatkozóan az osztályban szereplő függvényeket meg akarjuk adni. Fontos azonban éles különbséget tennünk a típusosztályok és az objektumorientált paradigmában megjelenő osztályok fogalmai között. Habár valóban vonható köztük valamilyen szinten párhuzam, a típusosztályok az objektumorientált terminológia szerint inkább absztrakt interfészeknek tekinthetőek. Meglepő módon azonban nem csak függvények, hanem konstansok (amelyek tulajdonképpen paraméter nélküli függvények) is lehetnek esetlegesen polimorfak. Erre példaként tekintsük az 1 konstanst: GHCi> :type 1 1 :: Num a => a Miért is pontosítanánk az 1 szimbólum típusát annál jobban, mint hogy azt mondjuk róla, az egy szám? Tekinthetnénk egész vagy lebegőpontos számnak egyaránt, a tényleges ábrázolásáról ez az írásmód nem ad információt. Az ábrázolás a használat során fog (lusta módon) egyre pontosabbá válni. Nézzük meg erre példaként a következő kifejezést: GHCi> :type 1 / 3 1 / 3 :: Fractional a => a Itt egy másik típusmegszorítás kerül elő, amely azt állítja, hogy az 1 / 3 nem egyszerűen valamilyen szám, hanem törtszám. A / (osztás) használata miatt kizártuk az egész számokat. A Fractional osztály a Num egy alosztálya, amely további megkötéseket tartalmaz a típusváltozóra: 24
GHCi> :info Fractional class Num a => Fractional a where (/) :: a -> a -> a recip :: a -> a fromRational :: Rational -> a -- Defined in ‘GHC.Real’ instance Fractional Float -- Defined in ‘GHC.Float’ instance Fractional Double -- Defined in ‘GHC.Float’ Hozzátesszük, hogy amikor az értelmezőben ki akarjuk egy ilyen kifejezés értékét számítani, az eredmény meghatározásához végül kénytelenek leszünk az osztályból valamelyik konkrét típust kiválasztani: GHCi> 1 / 3 0.3333333333333333 Ez az értelmező erre a célra beépített mechanizmusán keresztül történik, ahol a törtszámok esetében a Double típusra szűkített le. A :: használatával azonban lehetőségünk van a kifejezésekhez típusinformációt fűzni, és ezzel mi magunk is szabályozni tudjuk, hogy az adott polimorf típusból milyen konkrét, ún. monomorf típust hozzuk létre. GHCi> 1 / 3 :: Float 0.33333334 Ezt viszont nem szabad összetévesztenünk esetleg más programozási nyelvekből ismert típuskényszerítés fogalmával. A Haskell egy szigorúan típusos nyelv, ezért a típusrendszere nem engedi meg azt, hogy anélkül megváltoztassuk egy kifejezés típusát, hogy ne adnánk meg a régi és új típus közti konverziót végző függvényt (a kifejezés részeként). Ennek az elvnek az elhagyásával a rendszer nem lenne képes a programok helyességére garanciákat nyújtani. GHCi> (1 / 3 :: Float) :: Double :2:2: Couldn’t match expected type ‘Double’ with actual type ‘Float’ In the expression: (1 / 3 :: Float) :: Double In an equation for ‘it’: it = (1 / 3 :: Float) :: Double Szerencsére a számok különböző típusai között számos konverziós függvény elérhető. Ebben az esetben realToFrac használható a kívánt hatás elérésére: 25
GHCi> :type realToFrac realToFrac :: (Fractional b, Real a) => a -> b GHCi> realToFrac (1 / 3 :: Float) :: Double 0.3333333432674408 Ezzel együtt viszont az is rögvest nyilvánvalóvá válik, hogy ez csupán egy felületi kezelés. Mivel a számítást először alacsonyabb pontossággal hajtottuk végre, visszafordíthatatlanul információt veszítettünk. A típusrendszer az ilyen konverziók használatának kikényszerítésével tehát az ilyen és ehhez hasonló potenciális tévedésekre igyekszik felhívni a figyelmünket.
1.9. λ-függvények A funkcionális nyelvekkel kapcsolatban azt már tapasztalhattuk, hogy a függvények értékként szabadon használhatóak: átadhatóak paraméterként, képezhetőek eredményként. Azonban ennek egy további következménye, hogy a függvényeket mint értékeket nem kötelező névvel ellátnunk. Például az 1 és 3 értékeket anélkül használtuk fel az 1 / 3 kifejezésben, hogy azokat külön el kellett volna neveznünk. Mivel a függvények értékek, ez rájuk is érvényes, és az ún. λ (lambda) jelölés segítségével név nélkül is megadhatóak. Ezért a λ szimbólummal definiált függvényeket névtelen függvényeknek is szokás nevezni. A λ-függvények szemléltetéséhez most fogalmazzuk át a negate függvény definícióját a λ segítségével: negate = \x -> 0 - x Ebből kiderül, hogy Haskellben a λ jelet a gyakorlatban a \ (backslash) szimbólummal tudjuk a programjainkban leírni, és ez a függvény neve helyett szerepel. A λ tulajdonképpen egy kvantornak tekinthető, amely egy változónevet köt egy adott hatókörrel. Ezzel a kvantorral tudjuk megadni a definícióban, hogy milyen változókat szeretnénk használni, és ezeket a változókat a függvény törzsében hol kell helyettesíteni a függvény értékének kiszámítása, vagyis az alkalmazása során. A λ kvantor által kötött változókat a hatókörüktől egy -> (nyíl) szimbólum választja el. Ez nem azonos a korábban bemutatott típusoperátorral, csupán egy szintaktikai elem a nyelvben. A negate fenti definíciójában láthattuk tehát, hogy lényegében a \x -> 0 - x kifejezést (mint függvényt) nevesíti a negate szó. Tehát minden esetben, amikor a negate azonosítót használjuk a programunkban, ez a kifejezés kerül a helyére. Ezért ezt a helyettesítést akár mi magunk is elvégezhetjük az értelmezőben. 26
GHCi> :type \x -> 0 - x \x -> 0 - x :: Num a => a -> a GHCi> (\x -> 0 - x) 4 -4 Egymásba ágyazott λ-függvénnyekkel többparaméteres függvények is kifejezhetőek. Ebből most az is jobban látszik, hogy a λ kvantor vagy λ-absztrakció egy jobbasszociatív művelet, amely jól illeszkedik a korábbiakban megismertekhez: GHCi> :type (\x -> (\y -> x)) \x -> \y -> x :: a -> b -> a GHCi> (\x -> (\y -> x)) 1 2 1 Nem kötelező viszont a λ-függvényeket egymásba skatulyáznunk, a köztes nyilak mindig elhagyhatóak. GHCi> :type \x y -> x \x y -> x :: a -> b -> a GHCi> (\x y -> x) 1 2 1 A λ-absztrakciók segítségével nem kell minden egyes esetben külön függvényeket nevesítenünk, definiálnunk, amikor magasabbrendű függvényeket akarunk felparaméterezni. Ehhez érzékeltetésére vegyük például a length függvényt, amelyet egy lista hosszának a lemérésére használhatunk. Mivel ennek alapja a lista rekurzív bejárása, ezt most a foldr sémán keresztül fogalmazzuk meg úgy, hogy az első paraméterként átadni kívánt függvény törzsét a λ kvantorral egyszerűen beírjuk a helyére. length :: Num b => [a] -> b length xs = foldr (\_ n -> n + 1) 0 xs A definíció megértéséhez emlékezzünk vissza arra, hogy miként is működik a foldr. A paraméterként átadott kétparaméteres függvényünk első paraméterként mindig a lista soron következő elemét kapja meg, második paraméterként pedig a bejárás során görgetett érték aktuális állapotát. Az első paramétert most nem használjuk fel, ezért figyelmen kívül hagyjuk egy névtelen változóval, a második paraméter pedig a lista adott pontig mért hossza lesz. 27
Mindezek mellett a λ-jelölés azt is megengedi, hogy függvényeket építsünk függvényeken belül, vagyis függvény típusú eredményt képezzünk. Például egy ehhez hasonló függvény minden nehezség nélkül leírhatóvá válik Haskellben: actuator actuator | n < | n == | n >
:: Integer -> (Integer -> Integer) n 0 = \x -> x - 1 0 = \x -> x 0 = \x -> x + 1
Az actuator egy olyan függvény lesz, amely attól függően más függvényt ad vissza, hogy milyen egész számot adtunk meg paraméterként. Ha negatív, akkor a paraméterét eggyel csökkentő, ha nulla, akkor a paraméterét nem változtató, ha pozitív, akkor a paraméterét eggyel növelő függvényt hozunk létre. GHCi> (actuator 0) 5 5 GHCi> (actuator 1) 3 4 Másik érdekes, bár valamennyivel elvontabb példa az uncurry függvény. Előzőleg már megfigyelhettünk, hogy Haskellben a többparaméteres függvényeket ténylegesen egymásba ágyazott, egyparaméteres függvényekkel ábrázoljuk. Ezt Haskell B. Curry után "körrizésnek" nevezik. Curry egyike volt azoknak, akik annak idején lefektették a típusos funkcionális programozási nyelvek alapjait, és ő volt az, aki ezt a megoldást javasolta. Ezért az "uncurry" elnevezés a körrizett formáról a hagyományos, matematikában megszokott átalakításra utal. Ennek a fordítottját valósítja meg a curry függvény. A -> B -> C
--- uncurry --> <--- curry ----
(A, B) -> C
Ennek megfelelően íme az uncurry definíciója: uncurry :: (a -> b -> c) -> ((a, b) -> c) uncurry f = \(x,y) -> f x y
28
Itt tehát kapunk egy kétparaméteres függvényt, amelyet a definícióban úgy hívunk, hogy f. Ennek felhasználásával szerkesztünk egy olyan függvényt, amely egy rendezett párt kap paraméterül, mintaillesztés segítségével kiemeli annak egyes tagjait és külön átadja az f függvénynek. Látható, hogy a λ-jelölésben nem csak egyszerű változónevek szerepelhetnek, hanem lényegében tetszőleges minták. Így lehet használni: GHCi> :type uncurry replicate uncurry replicate :: (Num a, Ord a) => (a, b) -> [b] GHCi> (uncurry replicate) (3, True) [True,True,True] Megjegyezzük, a -> típusoperátor jobbasszociativitása miatt azonban az uncurry függvény úgy is írható, mintha kétparaméteres lenne: uncurry :: (a -> b -> c) -> (a, b) -> c uncurry f (x,y) = f x y Miután ennyit foglalkoztunk a λ-függvényekkel, hozzátesszük, hogy egy teljes logikai kalkulus, a λ-kalkulus épül köréjük. A λ-függvényeket és vele együtt a kalkulust Alonzo Church hozta létre az 1930-as években. A λkalkulus adja a Haskell matematikai hátterét, a számítási modelljét, vagyis a szemantikáját. Ennélfogva úgy is fogalmazhatnánk, hogy a λ-függvények feleltethetőek meg a funkcionális nyelvi programok gépi kódjának. Ebből fakadóan a nyelvek számos jellegzetessége, mint például a körrizés, innen eredeztethető. Másik ilyen különleges jellemző az ún. η-konverzió. Ez egy λ-függvényekre vonatkozó átalakítási szabály, amely a következő. (λx.E x) ↔η E amennyiben x nem fordul elő szabad változóként az E részkifejezésben. Ez bővebben kifejtve azt jelenti, hogy bármelyik λ-függvény, amelynek belsejében egy E részkifejezés mint függvény szerepel, ahol az x a paraméter, leegyszerűsíthető közvetlenül magára az E kifejezésre, amennyiben benne az x változó egyáltalán nem szerepel, vagy úgy szerepel, ha azt benne egy λ kvantor köti. Vagy, fordítva, egy függvénytörzs mindig kiegészíthető úgy egy kvantált változóval balról és jobbról, hogy az nem változtatja meg a viselkedését. Ennek értelmében például a következő egyszerűsítés megengedett: λx.(λx.x) x →η λx.x 29
miközben ez már nem: λx.(λy.x) x 6→η λy.x Az η-konverziót gyakran lehet alkalmazni rövidebb függvénydefiníciók gyártásához. Például a sum függvény foldr segítségével korábban megfogalmazott változata: sum’ :: Num a => [a] -> a sum’ xs = foldr (+) 0 xs így rövidíthető általa: sum’ :: Num a => [a] -> a sum’ = foldr (+) 0 Ha jobban megfigyeljük, itt köszön vissza ismét a parciális függvényalkalmazás. A foldr típusa ugyebár a következő: foldr :: (a -> b -> b) -> b -> [a] -> b Ennek adtunk most egy a -> b -> b típusú függvényt, a + operátort, amelynek típusa Num a => a -> a -> a, és ez így illeszthető ide: foldr (+) :: Num a => a -> [a] -> a Utána tudunk még adni neki egy számot, vagyis egy Num a => a értéket is, ez volt a 0: foldr (+) 0 :: [a] -> a Ez önmagában már egy függvény lesz. Ezért, ha azt egyszerűen elnevezzük valamilyen módon, ugyanúgy egy függvényünk lesz, nem kell külön neki átadni az utolsó paramétert.
1.10. Függvények kompozíciója Annak köszönhetően, hogy a függvények akár függvényt is vissza tudnak adni eredményként, Haskellben minden további nélkül meg tudjuk adni a matematikából ismert függvénykompozíció operátorát is:
30
infixr 9 . (.) :: (b -> c) -> (a -> b) -> (a -> c) f . g = \x -> f (g x) Ez a definíció az eddigiekhez képest a függvény definícióján és típusleíráson kívül tartalmaz egy újabb elemet, ez az infix kezdetű sor. Mivel egy infix operátort adtunk meg, vagyis egy olyan függvénynevet használtunk, amely szimbólumokból áll és az operandusai közé írjuk az alkalmazás során, lehetőségünk megadni annak kötési erősségét és irányát. Az előbbit úgy is nevezik, hogy az operátor precedenciája, az utóbbi pedig az asszociativitása. Haskell ilyen függvényeket is készíthetünk, és ezzel könnyebben (vagy olykor nehezebben) olvasható programokat tudunk írni. Az operátorok kötési jellemzőinek leírását tehát az infix kulcsszó után lehet megadni, pontosabban annak egyes változataival. A fenti esetben is megjelenő infixr azt jelenti, hogy egy jobbasszociatív operátort hozunk létre. Vagyis amikor a kifejezés kiértékelésekor egymás mellett azonos erősségű operátor áll, akkor közülük mindig a jobb oldalit kell választani. Ezután következik egy szám, amely az operátor kötési erősségét adja meg. Ez most így egy legerősebb, vagyis a leghamarabb kiértékelendő operátort ad meg. Ha nem írunk semmit, akkor a definíciónk mindig balra fognak kötni és a legerősebb szintre kerülnek. Ez megfelel a függvények általános értelmezésének. A függvénykompozíció művelete szorosan követi a matematikai megfelelőjét, amely a következő: (f ◦ g)(x) = f (g(x)) Az operátor így használható: GHCi> map ((\x -> x + 1) . (\x -> x * 2)) [1..5] [3,5,7,9,11] Ez lényegében teljesen ugyanaz, mintha eredetileg a következőt írtuk volna: GHCi> map (\x -> 2 * x + 1) [1..5] [3,5,7,9,11] Vagyis (ne feledjük, a függvénykompozíciót jobbról balra kell olvasni): (λx.x + 1) ◦ (λx.2 · x) ∼ (λx.2 · x + 1) Ebből fény derül arra is, hogy a λ-jelölés olykor csak megnehezíti a függvényszerű kifejezések írását. Ezért a Haskell nyelv kidolgozói hoztak egy 31
olyan jelölési szabályt, amely révén egyszerűen elhagyhatjuk a λ-függvényekből a változókat, kicsit olyan stílusban, mint amit már az η-konverzió esetében láthattunk. Például: ∼ ∼
(λx.x + 1) (λx.2 · x)
(+ 1) (2 ·)
Ezeket szeleteknek nevezik, és általuk a helyben komponált függvényeink valamelyest olvashatóbbá tehetőek: GHCi> map ((+ 1) . (* 2)) [1..5] [3,5,7,9,11] Ez a lehetőség további kísérletezgetésnek is ad valamennyit teret. A függvények összeillesztésének, komponálásának többféle módja is létezik. Például vegyük a következő függvényt: infixr 3 &&& (&&&) :: (a -> b1) -> (a -> b2) -> (a -> (b1, b2)) f &&& g = \x -> (f x, g x) A &&& (párhuzamos kompozíció) operátor egyszerre két függvényt alkalmaz ugyanarra az értékre, majd azok eredményeit egy rendezett párban adja vissza. Például: GHCi> ((+ 1) &&& (* 2)) 3 (4,6) Mindezeken túl a . és &&& függvények házasításával programok írásának egy nagyon érdekes módjára nyílik lehetőségünk. Ennek bemutatására tekintsünk most az average függvényt, amely listában felsorolt számok átlagát határozza meg: average :: Fractional a => [a] -> a average = uncurry (/) . (sum &&& length) Ez a függvény először egyszerre veszi a paraméterként kapott lista elemeinek összegét (sum) és a lista hosszát (length), majd az így kapott pár elemeire az uncurry segítségével alkalmazza a / függvényt. Az érthetőség megkönnyítésére nézzük meg a kompozícióban szereplő függvénydarabok típusait:
32
GHCi> :type (sum &&& length) (sum &&& length) :: (Num b2, Num a) => [a] -> (a, b2) GHCi> :type uncurry (/) uncurry (/) :: Fractional c => (c, c) -> c Valamint azok alkalmazásait: GHCi> (sum &&& length) [1..10] (55,10) GHCi> uncurry (/) (55,10) 5.5 GHCi> average [1..10] 5.5 Ennek a programozási stílusnak a sajátossága, hogy ilyenkor a definícióban sosem nevezzük meg magát a függvény paraméterét. Ezért nevezik ezt paramétermentes vagy néma programozásnak. Ennek a megközelítésnek később, a monadikus programozás megértése során lesz jelentősége.
1.11. Listák mint halmazok Az average függvény felhasználásával olyan függvényt is tudunk készíteni, amelyik képes kiszámítani az elemek átlagtól való átlagos eltérését egy listán belül. Ehhez először ki kell számítanunk a listabeli elemek átlagát, majd minden egyes elemre vonatkozóan meg kell határoznunk a tőle való eltérés abszolút értékét, majd ennek venni az átlagát. averageDeviation :: (Ord a, Fractional a) => [a] -> a averageDeviation xs = average [ abs (x - (average xs)) | x <- xs ] A definíció során alkalmazhattuk volna a listák feldolgozására a rekurziós megoldást. Azonban érdemes tudni, hogy a nyelv ennek elkerülésére, az érhetőség megkönnyítésére ajánl egy újabb jelölési segítséget, az ún. halmazkifejezéseket. A halmazkifejezések a Zermelo-Fraenkel-féle halmazelméletben, a halmazok leírására alkalmazott módszert veszik át, ahol a halmazokat (jelen esetünkben listákat) egy karakterisztikus függvénnyel adunk meg. Például az alábbi formula a páros számok négyzetének halmazát fogalmazza meg ezen a módon: { x2 | x ∈ N, x páros } Haskellben ez a stílus szinte egy az egyben megtartható. 33
[ x^2 | x <- [0..], even x ] Itt a [0..] lista megfeleltethető a természetes számok halmazának. Ez egy olyan lista, amely nullától indulva, egyesével növekvőleg tartalmaz egész számokat. Mivel nem adtuk meg a felsorolás felső korlátját, ez a lista gyakorlatilag végtelen hosszú lesz. A korábbiakból már tudjuk, hogy Haskellben ez nem lehetetlen. Mellette a even logikai függvénnyel válogatjuk a listából a páros elemeket, majd a ^ (kalap) operátor végzi a listából származó értékek négyzetre emelését. Azonban mindenképpen hozzá kell tennünk, hogy a Haskell esetében valójában nem halmazzal dolgozunk, hanem egy listával. Ennek következményeképpen az elemek benne akár ismétlődhetnek is, valamint a sorrendjük kötött. Ennélfogva bizonyos, a halmazelméletben teljesen átlagos halmazabsztrakciók nem teljesen ugyanúgy fognak viselkedni. Mint például az alábbi: { (x, y) | x ∈ N, y ∈ N } amelynek a Haskellbeli megfelelőjének a következőt gondolnánk: [ (x,y) | x <- [0..], y <- [0..] ] Elméletileg ez nem több, mint a természetes számok halmaza (N) felett értelmezett Descartes-szorzat, amelynek elemei ilyen párok. Azonban Haskellben a <- (balra nyíl) szimbólumot inkább úgy kell elképzelnünk, mint egy iterációt, amely az elejétől indulva, egyenként végigmegy a jobb oldali paramétereként megadott lista összes elemén. Ezzel az operátorral így listák bejárásának egymásba ágyazott ciklusait hozzuk létre. Véges listák esetében ez remekül meg is figyelhető: GHCi> [ (x,y) | x <- [1..3], y <- [1..3] ] [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)] amely írtható akár így is, ekkor jobban látszódik az egymásba ágyazódás: GHCi> [ [ (x, y) | y <- [1..3] ] | x <- [1..3] ] [[(1,1),(1,2),(1,3)],[(2,1),(2,2),(2,3)],[(3,1),(3,2),(3,3)]] Ekkor a listákban szereplő elemek összes lehetséges kombinációját hozzuk létre rendezett párok formájában. Ebből derül ki az is, hogy miért nem tanácsos (bár lehetséges) végtelen listáknál ezt a gondolkodást alkalmazni. Az egymásba ágyazás során először mindig a később, ebben az esetben a másodikként megadott listát járjuk be végig, és csak utána lépünk a korábbi, 34
vagyis itt az első, listában a következő elemere, amikor azon végigértünk. Ez végtelen listák esetében nem következik be soha, ezért a korábban megadott felsorolások ekkor lényegében nem fognak tudni működni. Megjegyezzük, egyetlen lista esetében a halmazkifejezések csupán egyetlen függvénnyel történő használata nem lesz más, mint egy leképezés, vagyis a map függvény: map f xs = [ f x | x <- xs ] Például: GHCi> [ x + 1 | x <- [1..5] ] [2,3,4,5,6] ezzel lesz ekvivalens: GHCi> map (+ 1) [1..5] [2,3,4,5,6] A másik lehetőség, amikor csak egy vagy több logikai feltétel alapján szűrni akarjuk a lista elemeit. Ezt a filter magasabbrendű függvénnyel is ki tudjuk fejezni és fordítva: filter p xs = [ x | x <- xs, p x ] Például: GHCi> [ x | x <- [1..5], even x ] [2,4] ezzel lesz ekvivalens: GHCi> filter even [1..5] [2,4] A kettő kombinációja pedig a map és filter függvények kompozíciójával leírható: GHCi> [ x + 1 | x <- [1..5], even x ] [3,5] GHCi> map (+ 1) (filter even [1..5]) [3,5] 35
1.12. Lokális definíciók Annak ellenére, hogy a Haskell és a tisztán funkcionális programozás a jelek szerint erős kapcsolatot ápol a matematikával, nyomokban felfedezhetünk eltéréseket. Mint minden programozási nyelv, a funkcionális nyelvek is arra valóak, hogy algoritmusokat, számításokat írjunk le bennük. Ezeknek pedig olyanoknak kell lenniük, amelyet a számítógép is képes minden külső segítség nélkül, önállóan elvégezni. Ehhez gyakran a matematika vonatkozásában elfogadott absztrakciókból, a valóságtól való elrugaszkodásból valamennyire fel kell adnunk, mert enélkül ezt a célt nem tudnánk megszolgálni. Ezért a funkcionális programokban is jelentőséggel bír egyrészt a kiszámíthatóság fogalma. Vagyis képesek vagyunk-e egy matematikai kérdést megfogalmaznunk, hogy egy tudatlan számítógép is képes legyen önállóan megadni rá a választ. Másrészt gyakran fontos mérlegelnünk azt is, hogy milyen gyorsan képes a programunk által előállítani a választ. Vagyis még a tisztán funkcionális programok esetében is felmerül a hatékonyság problémaköre. Például, idézzük fel az averageDeviation függvény előbbi definícióját: averageDeviation :: (Ord a, Fractional a) => [a] -> a averageDeviation xs = average [ abs (x - (average xs)) | x <- xs ] Ez remekül működik, azonban nem a lehető leghatékonyabb változat. Az average xs részkifejezést ugyanis, mivel nem mondtunk mást, minden egyes lépésben újra és újra kiértékeljük, miközben tudjuk, hogy az eredménye nem fog megváltozni menet közben. Ezért jó lenne, ha valahogy arra tudnánk kérni a rendszert, hogy jegyezze meg ezt a részeredményt, és amikor szükség van rá, ne számoljon semmit újra, egyszerűen csak húzza elő a memóriából. Ezzel a technikával kapcsolatban érdemes megjegyezni, hogy szinte minden programozási nyelvben működik, hiszen az a leggyorsabb számítás, amit már nem kell elvégeznünk. Ezért is jellemző az, hogy a gyorsabb programok nagyobb memóriaigénnyel rendelkeznek, mivel pontosan emiatt igyekeznek minden készen, a memóriában tartani. Haskellben a részkifejezések eredményeinek külön történő kiszámítására és azon tárolására a where kulcsszó használata. Ennek segítségével a definíciókon belül aldefiníciókat, ún. lokális definíciókat tudunk létrehozni. Így nem csak gyorsabb, de gyakran rövidebb és könnyebben karbantarható programokat kapunk. Most tekintsük a where használatára egy példát az averageDeviation esetében: averageDeviation :: (Ord a, Fractional a) => [a] -> a 36
averageDeviation xs = average [ abs (x - mean) | x <- xs ] where mean = average xs Itt tehát a mean fogja tárolni az average xs értékét, csak egyszer kell azt kiszámítani. Ne feledjük, mivel a where kulcsszóval kezdődő sor még mindig a definícióhoz tartozik, a margószabály értelmében bentebb kell húznunk. Továbbá érdemes tudni, hogy a lokális definíciók mindig el tudják érni a velük egy szinten levő, többi lokális definíciót, illetve annak a definíciónak a neveit, amelyben szerepelnek. Ez utóbbiak számukra globális nevek. Így a lokális definíciók képesek az ezeket tartalmazó definíciókkal is információkat megosztani, amely által a programok még tovább rövidíthetőek. Ennek demonstrálására vegyük a foldr ilyen módon átírt változatát: foldr f z xs = go xs where go [] = z go (x:xs) = f x (go xs) A where kulcsszó ezen felül még kombinálható mintaillesztéssel is, így olyan függvényeket is nagyon szépen meg tudunk adni vele, mint például a partition. Ez egy magasabbrendű függvény, amely paraméterként egy logikai függvényt és egy listát vesz, és a listából listák rendezett párját állítja elő úgy, hogy az elsőbe azokat az elemeket teszi, amelyekre igaz a logikai függvény, a másodikba pedig azokat, amelyekre nem. partition :: (a -> Bool) -> [a] -> ([a], [a]) partition p [] = ([], []) partition p (x:xs) | p x = (x:xs1,xs2) | otherwise = (xs1,x:xs2) where (xs1,xs2) = partition p xs Így próbálható ki az értelmezőben: GHCi> partition even [1..5] ([2,4],[1,3,5]) Ezt a függvényt csak nagyon bonyolultan lehetett volna összeállítani a where használata nélkül. Láthatjuk viszont, hogy a mintaillesztéssel kiegészítve lehetőségünk adódik a rekurzív hívásból származó pár egyes elemeit külön-külön elnevezni, miközben magát a párt nem nevezzük meg. 37
1.13. Interakció a külvilággal Tisztán funkcionális nyelveken természetesen nem csak egy értelmezővel tudunk kifejezéseken keresztül társalogni, hanem akár önálló, futtatható programokat is készíthetünk. Ezzel kapcsolatban persze kérdezhetnénk, ez pontosan miként is valósul meg. Tisztán funkcionális esetben az értelmezőtől függetlenül is futni képes programoknak van egy kitüntetett, ún. start kifejezésük, amely kiértékelése felel majd meg a futásnak. Ebben egy futtató környezet segédkezik, amelyet a programokhoz a fordítás során szoktak hozzácsatolni. Ez nem más, mint olyan rutinok halmaza, amelyek támogatást nyújtanak a nyelvben megjelenő egyes absztrakciókhoz. Ezek között szerepel az is, amikor az operációs rendszertől átveszi az irányítást, és megkezdi a start kifejezés értékének meghatározását. Ezt a feladatot még annyival szokták kiegészíteni, hogy a kiértékelés paraméterként megkapja a program környezetét és elérhetővé teszi minden olyan programrész számára, amelynek szüksége van rá. Például innen lehet lekérdezni a programnak a parancssorban átadott paramétereket, a környezeti változókat vagy állományokat elérni a rendszeren. A Clean programozási nyelv esetében ezt a környezetet közvetlenül, ténylegesen egy paraméter formájában kapja meg a kezdeti kifejezés. Haskellben esetében ezt a paramétert viszont ügyesen el lehet rejteni monádok alkalmazásával, számítási környezetek modellezésével. Ennek részleteit most nem fejtjük ki. Helyette egyszerűen tekintsük úgy, hogy van egy IO nevű paraméteres típus. Ez hasonlít például a lista típusához, ahol a paraméter azt adta meg, hogy a lista milyen típusú elemeket tárol. Itt az IO paramétere azt fogja megadni, hogy milyen típusú értéket tudunk kiszámítani az IO kontextuson keresztül. Maga ez a kontextus a program teljes környezetére utal, vagyis ha egy függvényt ezen keresztül értékelünk ki, lehetőségünk van hozzáférni a környezet elemeihez, vagy éppen azokat módosítani. Mivel az így keletkező viselkedés eléggé szerteágazó lehet, az IO típussal megfogalmazott számításokat mellékhatásosnak is szoktuk tekinteni. A mellékhatások megértéséhez most tekintsünk egy paraméter nélküli tiszta függvényt, egy konstanst: GHCi> :type "foobar" "foobar" :: String GHCi> "foobar" "foobar" GHCi> "foobar" "foobar" 38
Minden alkalommal, amikor ezt a konstanst kiértékeljük, tökéletesen ugyanazt az eredményt fogja adni, ahogy azt a tiszta függvénytől elvárjuk. Most azonban vegyünk egy mellékhatással rendelkező konstanst: GHCi> :type getLine getLine :: IO String GHCi> getLine hello! "hello!" GHCi> getLine yello! "yello!" Ez azért történik, mert a getLine maga nem egyszerűen egy függvény, hanem egy akció, pontosabban egy IO-akció. Az akciók abban térnek el a függvényektől, hogy az eredményük kinyeréséhez le kell futtatni ezeket. Az értelmező beépítetten támogatja az IO akció futtatását. Automatikusan át tudja adni a futtatandó akciónak a (számunkra láthatatlan) programkörnyezetet, amelyek többek között tartalmazza a szabványos bemenet pufferének állapotát. Így először a felhasználótól várja, hogy begépeljen valamit, majd az Enter billentyű megnyomása után azt a getLine akciónak átadja. Az IO típus segítségével tehát a típusban lehetőségünk van kódolni azt is, hogy az adott értékek kiszámítása milyen környezeteket, hatásokat igényel. Ezzel a programokban egyértelműen elkülöníthetővé válnak a tiszta és a nem tiszta részek, nem lesznek keverhetőek. Az IO esetében nincs olyan függvény, amely képes lejátszani annak hatásait a programon belül. Ezt majd a futtató környezet fogja a start kifejezés meghívásakor egyszerre elvégezni. Haskellben a start kifejezés neve main. Például tegyünk fel, hogy a korábban bemutatott függvények köré szeretnénk építeni egy parancssoros programot. Ez a program beolvassa a parancssorban megadott paramétereket, és mivel azok szöveges formában állnak rendelkezésre, átalakítja azokat egész számokká, majd kiszámítja az átlagtól való átlagos eltérésüket. Az eredményt végül a szabványos kimeneten fogja megjeleníteni. main :: IO () main = do args <- getArgs let xs = [ read x | x <- args ] print (averageDeviation xs) Láthatjuk, hogy a main típusa IO (). Ez arra utal, hogy ez egy mellékhatással rendelkező függvény, amely nem ad vissza semmilyen értéket. Pontosabban visszaad valamilyen értéket, ezt jelöli a (), de ennek a típusnak csak 39
egyetlen eleme van, a (). Ezért ezt a típust a más nyelvekből már ismerős void típusnak tekinthetjük. Ennek megfelelően a main egy void függvény, egy eljárás. A main törzsét egy, az akciók esetén használható írásmóddal, az ún. do szintaktika segítségével adtuk meg. A pontos részletekkel egyelőre itt még nem foglalkozunk, de hozzátesszük, ez az írásmód elsőre megtévesztő lehet. Sokan ugyanis hajlamosak azt hinni, hogy így imperatív stílusú programrészleteket tudunk beágyazni. A mostani példánk erejéig ez az analógia talán még meg is állja valamennyire a helyét, azonban nem árt tudni, hogy ez ennél jóval többet jelent. A do jelölés szerepe valójában az, hogy a mellékhatással rendelkező akciókból blokkokat tudjunk építeni. Az akciókból képzett blokkokban aztán az egyes akciók által kiszámított értékek megfoghatóak és felhasználhatóak más akciók paramétereiként. Továbbá vegyük észre, hogy ilyenkor is számít a tördelés, mivel a blokk egyes sorainak ugyanabban az oszlopban kell kezdődniük. Cserébe így se nem kell minden sor végére kitennünk pontosvesszőket, se nem kell blokkzárójeleket alkalmaznunk. Amikor egy blokkon belül akarjunk valamelyik számítás eredményét megjegyezni, a <- (kötés) operátort alkalmazzuk. Erre úgy is tekinthetünk, mint egy értékadásra, például := operátorra. Ennek értelmében a példában szereplő blokk első sora az imperatív gondolkodás szerint a következőképpen értelmezhető: args := getArgs A getArgs akció egy újabb mellékhatással rendelkező konstans, amely az éppen futó program parancssori paramétereit adja meg. Ez az értékadás magától létrehoz egy args nevű változót, nincs szükség arra, hogy külön deklaráljuk. A típusát ugyanazon az módon ki tudja sok esetben következtetni a fordító, amelyet már korábban láttunk. A getArgs konstans System.Environment modulból érhető el. Az egyes modulokban található függvényeket és értékeket az import kulcsszóval tudjuk elérhetővé tenni. Az import sorokat a forráskód elejére kell beszúrni, de akár az értelmezőben is kiadhatjuk: import System.Environment Érdemes tudni, hogy a mellékhatással nem rendelkező függvények közvetlenül nem adhatóak hozzá mellékhatásos blokkokhoz, mivel a típusuk nem fog illeszkedni. Ezért létezik egy függény, a return, amellyel képesek vagyunk beemelni tiszta kifejezéseket valameilyen számítási környezetbe. (Egyesek szerint a return emiatt nem is a legjobb elnevezés ennek a függvénynek, mivel a lift vagy inject találóbban leírná ezt a viselkedést.) 40
GHCi> :type return return :: Monad m => a -> m a Ebben a típusban a Monad megszorítás utal a mellékhatásosságra, és így a return lényegében tetszőleges tiszta érték tetszőleges környezetbe beemelésére alkalmas. main :: IO () main = do args <- return [] print args return () A main ezen változata paraméterek egy tisztán konstans listájával dolgozik és közvetlenül egy () értéket ad vissza. Ebből a blokkból az utolsó sor tulajdonképpen el is hagyható, mivel a print akció önmaga egy ilyen értékkel tér vissza: GHCi> :type print print :: Show a => a -> IO () Ez pedig már teljesíti azt az intuitív elvárásunkat, hogy a blokk utolsó kifejezésének eredménye határozza meg a blokk visszatérési értékének a típusát. Megjegyezzünk viszont, hogy blokkon belül a tiszta értékek elnevezéséhez nem szükséges azokat beemelni és az <- operátorral kötni. Ezt a let kulcsszóval is meg tudjuk csinálni, ezért szerepelt ez fentebb, ez eredeti programunkban. A let feladata, hogy tiszta kifejezéseknek lehessen vele neveket adni, hasonlóan a where kulcsszóhoz. Azonban a blokkokban számít a kifejezések megadásának sorrendje, és a let ugyanúgy egy új változó bevezetésére használatos. A programban az xs fogja hivatkozni a parancssori paraméterek egész számokká alakított változatait. Magát az átalakítást egy halmazkifejezéssel végezzük, amely bejárja az args lista elemeit, majd egyesével leképezi azokat szövegből számmá. Az átalakítást a polimorf read függvény végzi: GHCi> :type read read :: Read a => String -> a A read is egy túlterhelt név, és minden olyan típus esetén működik, amely eleme a Read típusosztálynak. Egy szöveget kap paraméterül, majd úgy próbálja azt értelmezni, mintha az az adott típus valamelyik elemének szöveges ábrázolása lenne. Figyeljük meg azonban, hogy ez a függvény a visszatérési értékében polimorf típusú, ezért annak pontosításához nagyon gyakran további információkra van szükség. 41
GHCi> read "42" *** Exception: Prelude.read: no parse Ez az értelmező esetében elég könnyen rosszul jöhet ki, mivel az a belső mechanizmusa miatt nem éppen azt a típust választja, amelyre elsőként gondolnánk. Ebben az esetben a () típus volt például az alapértelmezett. GHCi> read "()" () Fordítási időben azonban az ilyen esetekben hibát fogunk kapni a típusellenőrzőtől, mivel a típusváltozó értéke nem egyértelmű, nem lehet monomorffá tenni külső segítség nélkül. Természetesen, amennyiben hozzátesszük a kifejezéshez a megfelelő specializációt, működni fog: GHCi> read "42" :: Integer 42 A Haskell alapkönyvtárában, a Prelude-ben található Read példányok egészen jól használhatóak, segítségükkel akár sokkal összetettebb kifejezéseket is be lehet olvastatni. Mint például a következőt: GHCi> read "([(1, True)], [(’x’, 3.14)])" :: ([(Integer,Bool)], [(Char,Double)]) ([(1,True)],[(’x’,3.14)]) A main függvény a :main paranccsal akár közvetlenül az értelmezőből is meghívható: GHCi> :main 1 2 3 4 5 6 7 8 9 10 2.5 De természetesen a komplett forráskódot is le tudjuk fordítani a GHC segítségével egy független végrehajtható állománnyá. A GHC támogatja a több modulból álló programok fordítását is, képes magától megtalálni a hivatkozott modulokat. Ennek egyedüli feltétele, hogy a modulok forrásainak a hierarchiájuknak megfelelő könyvtárszerkezetben kell elhelyezkedniük, hasonlóan a Javaban írt programok esetéhez. Tehát például, ha egy modul neve A.B.C, akkor annak forrásának a A/B/C.hs állományban kell lennie ahhoz a könyvtárhoz képest, ahol a fordítást elkezdtük. $ ghc Tutorial.hs [1 of 1] Compiling Main ( Tutorial.hs, Tutorial.o ) Linking Main ... $ ./Tutorial 1 2 3 4 5 6 7 8 9 10 2.5 42
1.14. Összefoglalás Ebben a fejezetben tehát kaphattunk a Haskell programozási nyelven keresztül egy tömör ízelítőt abból, hogy miként is néz ki a tisztán funkcionális programozás a gyakorlatban. Elindultunk egy egyszerű függvénydefiníciótól és a végén láthattunk, hogy miként készíthetünk akár önállóan futtatható programokat is ezen a módon. Megismerhettünk valamennyire a funkcionális programozás elméleti háttereként szolgáló λ-kalkulust és kihasználtuk annak néhány jellegzetességét. Mellette az is kiderült, hogy a megszokott programszervezési szerkezetek, az elágazások, ciklusok, alprogramok ebben a gondolkodási stílusban miként jelennek meg. Továbbá használtunk a nyelvben már készen elérhető listákat, és ezek segítségével képesek voltuk matematikai halmazokat is modellezni. Röviden betekintést nyerhettünk a statikus, szigorú típusozás működésébe és tapasztalhattuk, az ehhez szükséges információkat miként képes a fordító akár magától kikövetkeztetni.
43
2. fejezet Típusok Ebben a fejezetben a típusokkal foglalkozunk. Bemutatjuk, milyen módokon lehet a programjainkban saját típusokat definiálni, valamint ezen keresztül igyekszünk azt is illusztrálni, hogy miként lehet ezek segítségével jobb, megbízhatóbb programokat készíteni. Ennek során az előző fejezetekben megismert alapokra fogunk építkezni, és hozzáadjuk mindazokat a szükséges ismereteket, amelyek a következő, a monadikus programozással foglalkozó fejezet megértéséhez és elsajátításához fognak majd kelleni.
2.1. Bevezetés Tisztán funkcionális nyelvekben a típusok definíciója fontos absztrakciós eszköz, amelynek köszönhetően pontosabb specifikációt tudunk megadni a programjaink részére. Mind a Clean, mind a Haskell szigorú, statikus típusos programozási nyelvek, amelyek mindkét aspektusában erősen támaszkodnak a típusok jelenlétére és azok megfelelő illeszkedésére. Ezért elsőként célszerű ezek mibenlétének tisztázása. – Szigorú típusozás alatt azt érthetjük, hogy a programbeli kifejezések típusa csak explicit típuskonverzió segítségével változtatható. – Statikus típusozás alatt azt érthetjük, hogy a programbeli kifejezések típusa fordítási időben ismert, amely segít a program logikai konzisztenciájának megtartásában, valamint a fordító számára szolgáltat (szemantikai) többletinformációkat a hatékonyabb fordításhoz, optimalizációhoz, megkönnyíti a specifikálást, dokumentálást. Emiatt teljesen kézenfekvőnek tűnik, hogy a felhasználó számára is nyújtani kell valamilyen lehetőséget a programokban megjelenő típusok bővíté44
sére. Új típusokat több szinten lehet definiálni attól függően, hogy mekkora rugalmasságra, típushelyességre vagy szabadságra van szükségünk. Ezek a szintek a következők, egyszerűbbtől a bonyolultabbig haladva: nevesített típusok, származtatott típusok (csak Haskellben), algebrai típusok. A következőkben ezeken haladunk végig egyenként.
2.2. Nevesített típusok Nevesített típusok, vagy más néven szinonimák alkalmazására abban az esetben lehet szükségünk, amikor nem akarunk teljesen új típust létrehozni. Helyette inkább egy meglevő típusnak akarunk egy másik, a felhasználására jobban utaló, esetleg rövidebb nevet adni, esetleg típusok adott kombinációját elnevezni. Erre Haskellben a type kulcsszó használható, például: type String type Name type Complex
= [Char] = String = (Double, Double)
A típusdefiníciók esetében fontos hozzátenni, hogy a fordító elvárja a típusnevek nagybetűsítését. A típusdefiníciókban a kisbetűs azonosítók automatikusan típusváltozókat jelentenek. Ez a megoldás leginkább a C nyelv typedef kulcsszavához hasonlít, amikor lényegében ténylegesen nem hozunk létre másik típust. Ennek megfelelően a fordító sem tesz különbséget az egyenlőség bal és jobb oldala között. Ezt a Haskell értelmezőben is ki tudjuk próbálni. Itt a típusokkal való kísérletezgetés az értelmező :type vagy röviden :t parancsa használható. Ekkor a fordító a parancs után szereplő kifejezésnek megpróbálja levezetni a típusát és ennek segítségével ellenőrizni annak helyességét. Mivel a fordító képes magától a legáltalánosabb típust kikövetkeztetni, nem minden esetben kötelező azt megadni. Viszont, ha szeretnénk, akkor a :: (dupla kettőspont) operátorral a kifejezés részeként az értékhez kapcsolhatjuk az elfogadtatni kívánt típust. GHCi> type Name = String GHCi> :type "John" "John" :: [Char] GHCi> :type ("John" :: Name) ("John" :: Name) :: Name A nevesített típusdefiníciók sémaként is tudnak viselkedni, mivel lehet paraméterük is, hasonlóan egy függvényhez. Például: 45
type Two a = (a, a) type PredicateOn a = a -> Bool A Haskell értelmezőben: GHCi> type PredicateOn a = a -> Bool GHCi> :type even even :: Integral a => a -> Bool GHCi> :type (even :: PredicateOn Integer) (even :: PredicateOn Integer) :: PredicateOn Integer Akárcsak a függvénydefiníciók esetében, új változónevet a bal oldalon tudunk bevezetni, amelyre aztán a jobb oldalon tudunk hivatkozni. A jobb oldal szabad változóinak tehát szerepelnie kell a paraméterek között. Viszont lehet olyan paraméter, amelyet nem használunk fel: type T a = Int Ezt fantomtípusnak nevezik. Segítségével a típus (metainformáció) szintjén tudunk értékeket megkülönböztetni, noha a nevesített típusok esetén ez nem még alkalmazható. Erre hamarosan visszatérünk a származtatott típusoknál.
2.3. Származtatott típusok Haskellben a típusok nevesítésének egyfajta továbbfejlesztése az az eset, amikor egy új típust származtatunk egy már meglevőből. Ekkor ugyan még nem vagyunk képesek az eredeti típus értékeitől különbözőket létrehozni, azonban ez a konstrukció már megengedi, hogy új műveleteket társítsunk hozzá. Típusok származtatását a newtype kulcsszóval tudjuk megadni, például: newtype Name = N String Érdemes megfigyelni, hogy a fenti definíció jobb oldalán feltűnik az N azonosító, amelyet adatkonstruktornak, vagy röviden konstruktornak nevezük. Ez tulajdonképpen egy függvény, amely felhasználásával a kiinduló típus értékeiből elő tudjuk állítani a származtatott típus elemeit. Ez utóbbit explicit típuskonverziónak is tekinthetjük. A fenti példában az N típusa például a következő lesz: N :: String -> Name 46
A konstruktorok nevei, a típusokéhoz hasonlóan, konvenció szerint nagybetűvel kezdődnek, valamint a fordítási egységen belül típusonként egyedeinek kell lenniük. Továbbá a típusok származtatása esetén a konstruktornak pontosan egy paramétere lehet. Ez szemléletesen szólva az eredeti típus egyfajta címkézését jelenti, Haskellben nagyon gyakran alkalmazzák. A fordító az így képzett címkéket teljesen külön típusnak fogja tekinteni a típusellenőrzés során, azonban a kódgenerálásnál már az őstípussal azonosan fogja kezelni. Ez a megkülönböztetés tehát alapvetően logikai, a programozó számára hasznos elszigetelés, a program hatékonyáságát nem befolyásolja. Tehát, a definícióban szereplő „címkefüggvény” segítségével tudunk az új típushoz tartozó értékeket gyártani, például a Name esetén: x :: Name x = N "foobar" Érdemes megjegyezni, hogy ilyenkor a következő állítás már nem teljesül, sőt, nem is lesz típusozható: GHCi> "foobar" == (N "foobar") :3:14: Couldn’t match expected type ‘[Char]’ with actual type ‘Name’ In the second argument of ‘(==)’, namely ‘(N "foobar")’ In the expression: "foobar" == (N "foobar") Korábban, a type használatánál észrevehettünk, hogy mivel ott a két típus között nincs különbség, az őstípus műveletei gond nélkül alkalmazhatóak a nevesített típus elmeire is. Ellenben, amikor származtatunk egy típust, ez az egybeesés megszűnik, így az őstípus műveleteit nem kapjuk meg ingyen: GHCi> (N "foobar") == (N "foobar") :4:14: No instance for (Eq Name) arising from a use of ‘==’ In the expression: (N "foobar") == (N "foobar") In an equation for ‘it’: it = (N "foobar") == (N "foobar") Minden egyes műveletet újra kell ezért definiálni a származtatott típusra. Ezzel együtt előnye viszont, hogy teljesen tiszta lappal indulunk. Olykor pontosan ezt használják ki a származtatott típusok alkalmazásával, ún. csomagolótípusokat szoktak ezen a módon gyártani. 47
Megjegyezzük, hogy a Haskell 98 szabványnak köszönhetően azonban bizonyos műveletek a típussal együtt származtathatóak. Ilyenek azok az (eseti) poliform műveletek, amelyek a különböző típusosztályokhoz kötődnek Haskellben. Például: egyenlőségvizsgálat (Eq), összehasonlítás (Ord), vagy a szöveggé alakítás (Show). Ezt a deriving kulcsszó használatával kérhetjük a típus definíciójában. newtype Name = N String deriving (Eq, Show) Ekkor a fenti összehasonlítás már működni fog, illetve az értékek megjeleníthetővé válnak az értelmezőben. Ilyenkor természetesen egy beépített heurisztika alapján jönnek létre a származtatott függvények, amely nem feltétlenül felelnek meg az elvárásainknak. Ahhoz viszont, hogy saját műveleteket tudjuk megadni a származtatott típushoz, valamilyen módon képesnek kell lennünk hozzáférni a felcímkézett értékekhez, a címke eltávolításával, hiszen tényleges műveleteket továbbra is az őstípus elemeivel tudunk végezni. Ennek eszköze a mintaillesztés. A mintaillesztés lényege, hogy a paraméterként kapott értékre egy adott mintát illesztünk, és amennyiben az illeszkedik, úgy annak egyes részeit külön nevekkel tudjuk hivatkozni. Természetesen az egyes részek elnevezése nem kötelező, a mintaillesztést gyakran egyszerű egyenlőségvizsgálatra alkalmazzák. A mintának lehet része maga a konstruktor is. Ennek alkalmazására példaként tekinthetjük az alábbi függvényt, ahol az akarjuk megvizsgálni, hogy egy név, vagyis Name típusú érték megfelelő-e. Ez szöveget akkor tekintünk megfelelőnek, amennyiben nem üres, nagybetűvel kezdődik és nem tartalmaz számjegyet. isValidName :: Name -> Bool isValidName (N (c:cs)) = isUpper c && all (not . isDigit) cs isValidName _ = False Hasonló módon most már meg tudjuk adni akár Name típusú értékek összefűzését: infixr 5 ++| (++|) :: Name -> Name -> Name (N s1) ++| (N s2) = N (s1 ++ s2) Ezt így tudjuk használni az értelmezőben, miután lefordítottuk a programot: GHCi> (N "foo") ++| (N "bar") N "foobar" 48
Érdemes azonban hozzátenni, hogy önmagában az adatkonstruktorok alkalmazása még nem feltétlenül eredményez megbízhatóbb programokat. Hiába készítettünk ugyanis egy külön függvényt a Name típus elemeinek jólformáltságának ellenőrzésére (isValidName), mivel a konstruktor közvetlenül elérhető, bárki ennek a vizsgálatnak a megkerülésével készíteni tud vele Name értékeket. Ennek elkerülésére találták ki az ún. ügyes konstruktorokat. Ezekkel már meg lehet akadályozni a típushoz tartozó elvárásoknak meg nem felelő értékek létrehozását. mkName :: String -> Name mkName s | isValidName s = N s | otherwise = error "mkName: invalid value" Tehát a Name értékek létrehozására nem az N konstruktort kell majd a programozónak használnia, hanem az okosabb mkName függvényt. Ehhez a Name definícíóját tartalmazó modulban nem szabad az N nevet exportálnunk, hanem csak az mkName azonosító maradhat elérhető. Figyeljük meg, hogy a mkName függvényben szereplő vizsgálat azonban dinamikus, tehát futási időben történik! A fenti függvény emiatt valószínűleg parciális lesz, és a helytelen értékek átadása a kiértékelés, és így a program leállásához vezethet. A későbbiekben látni fogunk majd ennek elkerülésére eszközöket. Végül hozzátesszük, hogy a newtype esetében már alkalmazhatóak a fantomtípusok. A következő példának az az érdekessége, hogy bár ugyanazt az értéket (az egyest) tároljuk adatként, a típusparaméterek értékeinek eltérése miatt a típusellenőrző mégsem fogja egyezőnek tekinteni. GHCi> newtype P a = P Int GHCi> (P 1 :: P Char) == (P 1 :: P Bool) :3:21: Couldn’t match type ‘Bool’ with ‘Char’ Expected type: P Char Actual type: P Bool In the second argument of ‘(==)’, namely ‘(P 1 :: P Bool)’ In the expression: (P 1 :: P Char) == (P 1 :: P Bool) In an equation for ‘it’: it = (P 1 :: P Char) == (P 1 :: P Bool)
49
2.4. Algebrai adattípusok Láthattuk, a származtatott típusok esetén már képesek vagyunk úgy egy újabb típust létrehozni, hogy megadhatóak mellette annak műveletei is. Viszont értékei tekintetében még továbbra is egy meglevő típusra építkezik. Az algebrai típusdefiníciók ebben az irányban lépnek tovább, és lehetőséget adnak a típushoz tartozó értékek leírására is. Az algebrai típusok nevüket onnan kapták, hogy az értékeket a generatív grammatikák szabályaihoz hasonlóan stílusban adjuk meg összeadás, szorzás, azok egységelemei és a fixpont műveletének segítségével. Az algebrai definíciókat Haskellben a data kulcsszó vezeti be, és ezekben az előbbieken kívül a newtype esetéhez hasonlóan itt is adatkonstruktorokat találunk. Az algebrai műveletek könnyebb megértéséhez most tekintsük csak a típusokhoz tartozó értékek készletét, amely lényegében halmazoknak feleltethetőek meg.
2.4.1. Típusok összeadása Elsőként az összeadás műveletét vezetjük be. Ezzel úgy tudunk típusokat építeni, hogy meglevőket összeadunk, vagyis azok értékkészleteit uniózzuk. Érdemes ezzel kapcsolatban azonban megemlíteni, hogy itt nem a matematikából ismert uniót kell szigorú értelemben vennünk, hanem annak egy speciális változatát, az ún. diszjunkt uniót. Ez az elnevezés arra a különbségtételre utal, hogy diszjunkt halmazokat kapcsolunk össze, vagyis olyan halmazokat, amelyeknek nincsenek közös elemeik. Ezt az algebrai típusok esetében úgy kényszerítik ki, hogy az összeadásban részvevő típushoz még egy címkét is hozzácsatolnak, és uniózzák ezeket. Emiatt a diszjunkt uniót olykor címkézett uniónak is nevezik. A címkék maguk a származtatott típusokhoz hasonlóan működnek, vagyis azok mindegyike egy-egy újabb adatkonstruktort jelent a definíció során. Ennek szemléltetésére vegyük most az X típust, amely nem tartalmaz egyetlen elemet sem. Erre vonatkozóan megjegyezzük, hogy ilyen típusokat a Haskell 98 szabvány szerint nem lehet létrehozni, azonban a GHC EmptyDataDecls kiterjesztésével ez lehetséges (ld. B.2. alfejezet). data X Mivel a típus nem tartalmaz egyetlen elemet sem, ezért értékek szintjén nem sokat tudunk vele kezdeni, nem tudunk ilyen típusú értéket megadni. Egyedül a további típusdefiníciókban tudjuk alkalmazni. Mint például az összeadásban, amelynek tulajdonképppen az egységeleme lesz, mivel annak hozzáadása nem változtatja meg a képzendő értékhalmazt. 50
Magát a címkézett uniót a címkék megadásával tudjuk definiálni, ahogy azt láthatjuk itt a T típus esetében: data T = A | B Ennek a típusnak két címkéje, konstruktora, vagyis eleme lesz, az A és a B. Ezek a konstruktorok gyakorlatilag már önmagukban egyelemű halmazokat jelentenek, amelyeknek maguk a címkék az elemei. A konstruktorokat az összeadást tartalmazó algebrai definíciókban a | (függőleges vonal) szimbólummal választjuk el. Ezeket már akár az értelmezőben is tudjuk ellenőrizni: GHCi> data T = A | B GHCi> :type A A :: T GHCi> :type B B :: T Ezt a felírási módot tekinthetjük úgy is, mint egy alternatíva szabályt, amely a konkrét értékek felírása során két vagy több (véges sok) konstruktor alkalmazása közti választási lehetőséget írja le. Az ilyen típusokat ezért felsorolásos típusnak nevezzük. Erre Haskellben egy jellemző példa a Bool típus definíciója: data Bool = True | False De mellette minden olyan típust le tudnánk elméletben ilyen módon írni, amelynek megszámolható eleme, többek között az Int vagy Char típusokat. Ezeket viszont hatékonysági megfontolásokból nem így szokták ábrázolni. Továbbá vegyük azt is észre, hogy az előbb bevezetett X típus valóban az összeadás egységeleme lesz. Hiába rendelünk hozzá címként a definícióban, nem tudunk X típusú elemet mondani, ezért az az alternatíva sosem lesz használható: data T = A | B | C X
2.4.2. Típusok szorzása Típusok szorzásáról akkor beszélünk, amikor egy konstruktornak több paramétere van. Erre lehet példa az, amikor a T típust ezen a módon adjuk meg:
51
data X = A | B data Y = C | D data T = T X Y Ekkor a T az X és Y elemeinek összes lehetséges kombinációjának révén keletkezik, azaz kétszer két, vagyis négy eleme lesz: T = { T A C, T B C, T A D, T B D } Ezeket rendezett n-seknek is szokás nevezni, ezért ez tulajdonképpen a matematikában a Descartes-szorzatnak feleltethető meg. Ez ugyanaz, mint amikor a rendezett n-eseket képező , (vessző) operátort alkalmazzuk. GHCi> :type (,) (,) :: a -> b -> (a, b) A szorzás műveletének egységeleme az egyelemű típus lesz, mivel azzal összeszorozva egy másik típust nem növekszik meg az eredménytípus elemeinek száma. data T = T Ekkor egy olyan T típust konstruálunk, amelynek egyetlen eleme van, a T konstans. Ennek a neve "unit" vagy egységtípus, amely Haskellben a (). C-szerű nyelvekben ez a void típusnak feleltethető meg leginkább. GHCi> :type () () :: ()
2.4.3. Rekurzív típusok Lehetőségünk van rekurzív típusok készítésére is. Ezt, hasonlóan a függvényekhez, egy fixpont típus segítségével adhatjuk meg. data F f = F (f (F f)) Ekkor lényegében az F típus paramétereként megadott típust alkalmazzuk saját magára egészen a végtelenségig. Ezt a belső típus úgy tudja lezárni, ha a definíciójában alkalmaz választási lehetőségeket, és benne olyan alternatívákat, ahol már nem hivatkozik saját magára. Ennek bemutatására nézzük most a láncolt listák definícióját! Esetükben tudjuk, hogy kétféleképpen építhetőek fel. Egyrészt az üres listával, amely önmagában a lista típus egy konstansa. Ezt most jelöljük a Nil értékkel. 52
Másrészt egy lista elé mindig oda tudunk fűzni egy elemet, egy fejet, amelyet a listához annak törzseként illesztünk. Ennek a konstruktorát nevezzük most úgy, hogy Cons. Mivel azonban a Cons második paramétere egy lista, valamilyen módon tudunk hivatkoznunk arra a definícióra, amelyben most vagyunk. Ezért felveszünk a lista elemeinek típusát leíró típusváltozó (a) mellett egy másikat is, amely ennek megadására használható (xs). Az így keletkező L típust aztán ha megadjuk az F típusnak, akkor leírhatóvá válik a lista típusa. Észrevehetjük azonban, hogy a Haskell megengedi a típusok parciális alkalmazát is. Így az L függvénynek csak az első paraméterét adjuk meg, a másodikat már nem kell, arról az F definíciója gondoskodik. Az egyszerűség kedvéért erre a kompozícióra bevezetjük a List nevesített típust. data L a xs = Nil | Cons a xs type List a = F (L a) Az értelmezőben ezt is ki tudjuk próbálni: GHCi> :type F Nil F Nil :: F (L a) GHCi> :type F (Cons True (F Nil)) F (Cons True (F Nil)) :: F (L Bool) Szerencsére a fordító nem kötelez minket ennek a formának az alkalmazására. Helyette a lista algebrai definícióját egyszerűen így is meg tudjuk fogalmazni: data List a = Nil | Cons a (List a)
-- [a] -- [] -- a : [a]
Ezt a definíciót így lehet alkalmazni: GHCi> :type Nil Nil :: List a GHCi> :type Cons True Nil Cons True Nil :: List Bool
53
2.4.4. Műveletek algebrai típusok elemeivel Az algebrai módon definiált típusok elemeit a származtatott típusokhoz hasonlóan mintaillesztéssel tudjuk megvizsgálni. Például, ha tekintjük a Bool típus korábban megadott definícióját, és ahhoz akarjuk a logikai konjunkció (&&) műveletét megadni: (&&) :: Bool -> Bool -> Bool True && True = True _ && _ = False Természetesen ilyenkor is alkalmazható a deriving kulcsszó bizonyos túlterhelt műveletek, vagyis típusosztályok (pl. Eq, Ord, Show) példányainak automatikus származtatására. Továbbá a mintaillesztés kihasználható listakifejezésekben is. Itt a screen egy olyan függvény, amely a logikai értékeket első komponensként tartalmazó párok listájából csak azokat azokat tartja meg, ahol a logikai érték True. screen :: [(Bool, a)] -> [a] screen xs = [ x | (True, x) <- xs ]
2.4.5. Struktúraszerű használat Amikor egy algebrai adattípusban szorzatokat használunk, egy idő után szükségünk lehet valamilyen hozzáférést nyújtó (beállító vagy lekérdező) függvényekre. Ehhez most tekintsünk egy példát! type Name type Age type Address
= String = Int = String
data Person = Person Name Age Address deriving (Eq, Show) Itt a személyeket adott tulajdonságaikkal leíró Person típust adtuk meg: név (name), kor (age) valamint cím (address). Maga a típus ezekenek a tulajdonságokat ábrázoló típusoknak lesz egy szorzata. Amikor egy új Person típusú értéket akarunk készíteni, egyszerűen csak meg kell adnunk a neki megfelelő konstruktor paramétereit. GHCi> :type Person Person :: Name -> Age -> Address -> Person GHCi> let dummy = Person "John Smith" 25 "London" GHCi> dummy Person "John Smith" 25 "London" 54
Az egyes mezőket megfelelő minták megadásával tudjuk kiemelni a Person típusú értékekből, amelyekre egyesével külön függvényeket kell így definiálnunk. name :: Person -> Name name (Person x _ _) = x age :: Person -> Age age (Person _ x _) = x address :: Person -> Address address (Person _ _ x) = x A függvények például így használhatóak: GHCi> age dummy 25 Az ilyen függvények automatikus származtatását hivatottak megvalósítani a típusdefinícióban szereplő kompensekhez kapcsolható mezőnevek. Ezeken keresztül a fenti definíció sokkal tömörebben is megfogható: data Person = Person { name :: Name , age :: Age , address :: Address } deriving (Eq, Show) Megjegyzendő viszont, hogy mezőneveknek, mivel függvényként viselkednek, az adott fordítási egységen belül egyedieknek kell lenniük. Ugyanez a felírás akkor is alkalmazható, amikor csupán bizonyos mezők értékeit szeretnénk módosítani másolás során. Mivel tisztán funkcionális nyelvekben a változók értékei nem íródnak felül, itt csupán egy újabb érték létrehozásáról lehet szó. movePerson :: Person -> Address -> Person movePerson p addr = p { address = addr } Ennek hagyományos megfelelője a következő lenne: movePerson :: Person -> Address -> Person movePerson (Person n a _) addr = Person (n a addr) 55
Valamint ez a szintaxis mintaillesztésben is alkalmazható: mayRetire :: Person -> Bool mayRetire (Person { age = x }) = (x > 65) Ennek megfelelője: mayRetire :: Person -> Bool mayRetire (Person _ x _) = (x > 65) A bemutatott szintaktikai kiegészítések előnye, hogy alkalmazásuk során a típus mezőinek sorrendje tetszőlegesen változtatható, újabb mezőkkel bővíthető anélkül, hogy a meglevő kódokat módosítani kellene. Ezzel együtt egy tömörebb leírást is lehetővé tesz.
2.4.6. Példák Paraméteres algebrai adattípusokkal már egészen hasznos és érdekes absztrakciókat tudunk készíteni. Az egyik közülük a Maybe típus. -- Maybe :: * -> * data Maybe a = Nothing | Just a deriving (Eq, Show) Így lehet használni: GHCi> :type Nothing Nothing :: Maybe a GHCi> :type Just Just :: a -> Maybe a GHCi> :type Just ’x’ Just ’x’ :: Maybe Char Segítségével opcionális értékeket tudunk kifejezni, vagyis lényegében egy tetszőleges típust tudunk kiegészíteni egy további elemmel, amely a Nothing. Ennek szerepe, hogy jelezze, ha a függvény nem ad vissza semmilyen értéket. Ezen keresztül a parciális függvényeket Haskellben totálissá tudjuk alakítani (a kiértékelés szempontjából), vagyis az érték hiánya esetén nem szakad meg a kiértékelés. Például így tudunk egy biztonságos osztást definiálni: infixl 7 ‘safeDiv‘ safeDiv :: Integral a => a -> a -> Maybe a _ ‘safeDiv‘ 0 = Nothing x ‘safeDiv‘ y = Just (x ‘div‘ y) 56
Látható, hogy nullával sosem fogunk osztani, hanem helyette automatikusan egy Nothing, avagy „érvénytelen” értéket generálunk. Ezzel a függvény alkalmazója értesül a hiba tényéről, és lehetősége van kezelni azt. Azaz szabályosan leállítani a programot, tájékoztatni róla a felhasználót, esetleg valamilyen módon megpróbálni elhárítani a hiba okát. Másik hasonlóan hasznos algebrai típus az Either, amelynek a segítségével két típust illesztünk össze úgy, hogy közülük mindig csak az egyiket tudjuk használni. -- Either :: * -> * -> * data Either a b = Left a | Right b Így lehet használni: GHCi> :type Left Left :: a -> Either a b GHCi> :type Left ’a’ Left ’a’ :: Either Char b GHCi> :type Right Right :: b -> Either a b GHCi> :type Right ’a’ Right ’a’ :: Either a Char Ezt a típust a Maybe javításaként is szokták alkalmazni, amikor nem csak annyit akarunk a függvényben visszaadni, hogy van érték vagy sem, hanem például a hiba okáról is bővebb információkat akarunk továbbítani a hívó felé. type Error a = Either String a infixl 7 ‘saveDiv‘ safeDiv :: Integral a => a -> a -> Error a _ ‘safeDiv‘ 0 = Left "safeDiv: division by zero" x ‘safeDiv‘ y = Right (x ‘div‘ y) Hagyományosan a Left konstruktor a hiba jelzésére szolgál, a Right pedig a helyes eredmény visszaadására. Mindezek mellett lehetőségünk rekurzív algebrai adattípusok segítségével leírni akár végtelen adatszerkezeteket is. Erre remek példa a természetes számok Peano szerinti (rekurzív) ábrázolása: -- Nat :: * data Nat = Zero | Succ Nat deriving (Eq, Show) 57
Ebben az esetben az értékeket így lehet képezni: GHCi> :type Zero Zero :: Nat GHCi> :type Succ Succ Zero :: Nat GHCi> :type Succ Succ (Succ Zero)
-- nulla Zero -- egy (Succ Zero) -- kettő :: Nat
Illetve ezen a módon lehetne megvalósítani az összeadást erre az ábrázolásra: add :: Nat -> Nat -> Nat Zero ‘add‘ m = m (Succ n) ‘add‘ m = Succ (n ‘add‘ m) Ezzel kapcsolatban megjegyezzük, hogy követi a matematikai felírást, ahol az összeadásra ezek a szabályok vonatkoznak: 0 + m = m (1 + n) + m = 1 + (n + m)
2.5. Üres értékek Minden típusnak van még egy további eleme, ez az ún. ⊥ (üres) érték. Ez azt jelöli, amikor egy kifejezésnek nincs értéke. Ilyen előfordulhat például parciális függvénynek alkalmazásakor, ki nem számítható (pl. végtelen rekurzív) értékek esetén, vagy kivételek kiváltódásakor. Haskellben ezt az undefined nevű konstans is tudja képviselni. GHCi> :type undefined undefined :: a GHCi> undefined *** Exception: Prelude.undefined
2.6. Fajták Mind a nevesített típusoknál, mind pedig az algebrai típusok esetén is tudunk absztrakt, paraméteres típusokat készíteni. Ezért ezeket típuskonstruktornak is szokták nevezni, mivel segítégükkel típusokból lehet újabb típusokat előállítani. 58
Ehhez kapcsolódóan a típusok rendelkeznek típussal, vagy ahogy gyakran mondják, fajtával, amely arra utal, hogy az adott típusnak mennyi szabad paramétere van. Ebből megállapítható az, hogy a szóbanforgó típus operátor vagy csak egy konstans. Ezt csillagok segítségével jelölik. Ha nincs egy típusnak szabad paramétere, akkor a hozzá tartozó fajtát egyetlen csillag jelöli. Ilyen például az Int. A fajtákra vonatkozó információt a :kind vagy röviden :k paranccsal kérdezhetjük le. GHCi> :kind Int Int :: * Az Int, mivel a fajtája egyszerűen csak *, típusnak nevezzük. Amikor egy típusnak van szabad paramétere (típusváltozója), akkor a fajta a következő alakú lesz, például a lista típuskonstruktorának esetében: GHCi> :kind [] [] :: * -> * Ekkor tehát egy típusoperátorról beszélünk. Másik hasonló operátor a függvények típusát alkotó -> (nyíl): GHCi> :kind (->) (->) :: * -> * -> * Konkrét elemeket csak * fajtájú típusokhoz tudunk rendelni, ezért alkalmazásuk előtt az absztrakt típusok szabad paramétereit, hasonlóan a függvényekéhez, a Curry-féle módszerrel tudjuk lépésenként megkötni: GHCi> :kind [] Int [] Int :: * GHCi> :kind Char -> Bool Char -> Bool :: *
2.7. Típusosztályok Adódhatnak olyan műveletek, amelyeket szeretnénk egyszerre több típusra is értelmezni. Ekkor lényegében adott egy szimbólumunk, amelyet szeretnénk túlterhelni. Azaz a több különböző típus esetén megírandó, eltérő implementációt rejtő függvényeknek egy közös nevet adni, és hagyni, hogy kizárólag a típus alapján válassza ki a fordító vagy a futtató rendszer közülük a megfelelőt. 59
Ezt nevezik eseti polimorfizmusnak, amikor egy név tényleges jelentése az alkalmazás helyétől függ. Ez az, amit általában a programozási nyelvekben egyszerűen csak polimorfizmusnak neveznek. Haskellben viszont az már találkozhattunk a polimorfizmus egy másik fajtájával, a parametrikus polimorfizmussal is. Ekkor az algoritmus nem változik a típustól függően, hanem egyszerűen független annak bizonyos komponenseitől, amelyeket típusváltozók beszúrásával teszünk szabaddá. Túlterhelt műveletek jellemzően a következők szoktak lenni: – egyenlőségvizsgálat, összehasonlítás (rendezhetőség), – szöveggé alakítás, beolvasás, – összeadás, szorzás, stb. különböző reprezentációjú számokon. Függvények túlterheléséhez típusosztályok kell megadunk. Az „osztály” elnevezés azonban elsőre megtévesztő lehet, mivel a típusosztályok nem azonosak az objektumorientált nyelvekben megszokott osztályokkal. Helyette inkább úgy fogalmazhatnánk, hogy a típusosztályok a Java nyelv interfész fogalmához állnak a legközelebb. A típusosztályok tulajdonképpen típusokat csoportosítanak valamilyen közös interfész szerint. A tartalmazott típusokat az osztály példányainak nevezzük. Egy típus több osztály példánya is lehet, valamint az osztályok tartalmazhatják is egymást. A példányok az osztály definíciójában megadott interfészt valósítják meg az adott típusra. Hasonlóan viszont a korábban bemutatott különböző típusdefiníciós lehetőségekhez, a típusosztályokat is széles körben lehet alkalmazni.
2.7.1. Típusosztályok mint szótárak Az intuíció megalapozásához most megadjuk a típusosztályok egy naïv implementációját algebrai adattípusok használhatával. Itt egy szótárt fogunk készíteni, ahova felvesszük az össze túlterhelni kívánt függvényünket. Például készítsünk egy olyan szótárat, amellyel egyenlőségvizsgálatot tudunk túlterhelni. Az equals függvény az egyenlőség, a notEquals ennek ellentétének vizsgálatára lesz alkalmazható. data Equals a = Equals { equals :: a -> a -> Bool , notEquals :: a -> a -> Bool }
60
Szemléltetésképpen ennek most adjuk egy lehetséges implementációját, egy példányát a Bool típusra az alábbi módon. eqBool = Equals { equals = where boolEquals True True boolEquals False False boolEquals _ _
boolNotEquals x y = not (boolEquals x y) Mindezeken keresztül aztán ezek a szótárak alkalmasak lesznek az alábbihoz hasonló függvények definiálására: compareList compareList compareList compareList
:: _ eq _
Equals [] (x:xs) _
a -> [a] [] = (y:ys) = _ =
-> [a] -> Bool True (equals eq) x y && compareList eq xs ys False
Ezt aztán a következő módokon tudjuk az értelmezőből meghívni: GHCi> compareList eqBool [True,True,False,False] [True,False,True,False] False A fordító tehát ezeknek a szótáraknak a szerkesztését és menedzselését veszi át tőlünk. Erre hozták létre az osztályokhoz és azok példányainak megadásához alkalmazható szintaktikai szerkezeteket a nyelvben.
2.7.2. Osztályok definíciója Miután algebrai adattípusok segítségével áttekintettük a típusosztályok lényegét, tekintsük a tényleges leírási móddal az egyenlőségvizsgálathoz tartozó Eq osztály definícióját: class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool Ebben az esetben a == és /= műveletek minden olyan típus esetén elérhetőek, amelyek helyettesíthetőek az a típusváltozó helyére. Ezt a helyettesíthetőséget példányok megadásával lehet irányítani, amelyeket külön nekünk kell a programban leírnunk, vagy a deriving kulcsszóval származtatni. A 61
típusváltozó helyettesíthetőségének ezt a fajta szűkítését korlátozott polimorfizmusnak is szokták nevezni. A típusosztályok alkalmazása tehát egy megszorítást tesz a típusban szereplő típusváltozókra, amely látható a típusban is. GHCi> :type (==) (==) :: Eq a => a -> a -> Bool GHCi> :type (/=) (/=) :: Eq a => a -> a -> Bool Viszont a megszorításokból közvetlenül még nem következik, hogy az adott függvény valamelyik típusosztály művelete, ugyanis ezek a korlátozások akkor is meg tudnak jelenni, ha a függvény definíciójában szerepel egy túlterhelt függvény. Erre példaként tekintsük egy olyan saját függvényt, amely megszámolja, hogy egy adott érték mennyiszer szerepel egy listában: count :: Eq a => a -> [a] -> Int count x = length . filter (== x) Ekkor a count maga nem lesz az Eq típusosztály eleme. Mivel azonban használja annak az == operátorát, a típusban eredetileg megjelenő a típusváltozó megkapja az Eq megszorítást. Az Eq definíciójában egyúttal valamennyire látható a típusosztály felírásának mikéntje. Típusosztályokat a class kulcsszóval vezetjük be, ezt követi egy típusváltozó. Ez az osztály fejléce, amelynek mindenképpen meg kell lennie. Az osztályok neveinek, a típusokéhoz hasonlóan nagybetűvel kell kezdődniük a konvenciók szerint. Az osztályokban alapvetően csak egyetlen típusváltozót enged meg a Haskell 98 szabvány, de MultiParamTypeClasses kiterjesztéssel akár többet is használhatunk (B.2. alfejezet). A típusosztály fejlécéhez a where kulcsszóval, behúzással csatolhatunk egy leírást, ahol a típusváltozó segítségével megadhatjuk azokat a függvényeket, amelyeket az adott osztályba tartozó típusokra meg kell valósítani. Ezeket a függvényeket metódusoknak is szokás nevezni. Fontos, ahogy az Eq esetében is láthattuk, hogy minden metódusnak legalább a típusát meg kell adnunk, és ezekben legalább egyszer hivatkoznunk kell a fejlécben szereplő típusváltozót. Enélkül az osztály alkalmazása értelmetlen lenne. A metódusok típusaihoz, vagy más néven absztrakt szignatúráihoz tartozhatnak alapértelmezett definíciók, amelyek megadása esetén a példányok definíciójában nem lesz majd kötelező szerepeltetni. Az osztályban a definícióval nem rendelkező metódusok képezik az ún. minimális definíciót, amelyek szükségesek egy működőképes példány megadásához. 62
Ennek megfelelően az Eq előbbi definíciója is tovább bővíthető az egyes műveletek alapértelmezett implementációjának megadásával. Sőt, a metódusok akár egymással is kifejezhetőek lesznek: class Eq a where (==) :: a -> a -> Bool x == y = not (x /= y) (/=) :: a -> a -> Bool x /= y = not (x == y) Észrevehetjük viszont, hogy ez lényegében egy kölcsönös, végtelen rekurziót jelent ebben a formájában. Ezért a két metódus közül legalább az egyiket mindenképpen javasolt felüldefiniálnunk, a másik pedig abból származtatható lesz. Erre vonatkozóan megjegyezzük, hogy a fordító engedi, hogy hiányos példánydefiníciókat adjuk meg, de ilyenkor mindig figyelmeztetést ad. Valamint, ha megpróbáljuk használni, akkor a kiértékelés megszakad. Érdemes tudni, hogy az osztályok fejlécében tehetünk további kikötéseket is a típusváltozóra. Ezzel lényegében egy osztály példányosítását egy vagy több másik osztály példányosításához köthetjük, ezáltal „örökölhetjük” azok metódusait is. Például ilyen az Ord osztály egy lehetsége definíciója, amely az egyes típusok rendezhetőségét írja le: class Eq a => Ord a where (<) :: a -> a -> Bool x < y = not (x >= y) (<=) :: a -> a -> Bool x <= y = (x < y) || (x == y) (>) :: a -> a -> Bool x > y = not (x =< y) (>=) :: a -> a -> Bool x >= y = (x > y) || (x == y) Ezen a módon egy másik típusosztály al-, vagy részosztályát írjuk le, maga az osztály pedig annak ősosztálya lesz. Több osztály is szerepelhet a megkötések között, ilyenkor mindazok metódusainak meglétét meg tudjuk követelni.
63
2.7.3. Példányok definíciója A típuossztályok példányait többféle módon készíthetjük el. Egyrészt a deriving kulcsszó segítségével megkérhetjük a fordítót, hogy automatikusan vezesse le nekünk ezeket, amennyiben lehetséges. Másrészt megadhatjuk mi magunk a példányt. Például vegyük a Bool típus példányát az Eq típusosztályra: instance Eq Bool True == True False == False _ == _
where = True = True = False
Ez alapján megfigyelhetjük, hogy a példányok megadásának módja körvonalaiban hasonlít maguk az osztályok megadásához. A példányok definícióját az instance kulcsszóval vezetjük be, ezt követi a példányosítani kívánt osztály neve, majd annak a típusnak a neve, amelyre végre akarjuk hajtani a példányosítást. Ezt a példány fejlécének nevezzük. Ezt opcionálisan lehet bővíteni az osztályban leírt metódusok definíciójának megadásával a where kulcsszót követően. A definíciók kapcsán hasznos hozzátenni, hogy ott már nem kell, és nem is tudunk típusdeklarációkat megadni, mivel azok az osztályban és a példányban megadott információkból maguktól következnek. A példányok definíciója bárhol megadható, ahol az osztály látszik. Ennek következménye, hogy az osztályok tulajdonképpen a végtelenségig bővíthetőek. Példányok általánosabban, típusváltozókat tartalmazó típusokra is felírhatóak, tekintsük csak a listákat erre példaként: instance [] (x:xs) _
Eq == == ==
a => Eq [a] where [] = True (y:ys) = (x == y) && (xs == ys) _ = False
Vegyük észre, hogy ilyenkor elvárjuk a listaelemekre vonatkozóan is, hogy létezzen egyenlőségvizsgálat, tehát a példányok fejlécében is megadhatóak a típusváltozókra további megkötések. Emiatt a fenti definícióban szereplő == szimbólum jelentése mindig függ az alkalmazás helyétől, vagyis a típusától. Amikor a listák fejeit hasonlítjuk össze, egy egyenlőségvizsgálatot jelent a lista elemeit jellemző a típusra. A listák törzseinek összevetésekor viszont ez egy rekurzív hívást jelöl közvetlenül magára a definiálandó függvényre. Ez a definíció egyben példa az ún. strukturális ekvivalenciára, vagyis akkor tekintjük egyenlőnek a két értéket, ha elemeik pontosan ugyanazok és ugyanabban a sorrendben szerepelnek. 64
2.7.4. Többértelmű nevek A túlterhelt függvények esetében olykor előfordulhat, hogy egyértelműen nem lehet az adott típuskörnyezetből megállapítani, melyik implementációt válasszuk a névhez. Például tekintsük a read függvényt. GHCi> :type read read :: Read a => String -> a Ennek az a feladata, hogy szövegből egy adott a típusú értéket állítson elő. Ez persze csak olyan a típusokra alkalmazható, amelyek a Read típusosztály tagjai, tehát valamilyen módszerünk az értékeik szöveges formából történő felismerésére. Ahogy a típusából még láthatjuk, a read maga egy egyparaméteres függvény, tehát csak azt a szöveget kell megadnunk, amelyet értelmezni szeretnénk. GHCi> read "42" *** Exception: Prelude.read: no parse Ha ezt például egy szám szöveges alakjával próbáljuk meg, akkor egy futási hibát kapunk, mely szerint az elemzés sikertelen volt. Ez viszont csak az értelmezőben van így, mivel ha egy ilyen kifejezést tartalmazó kifejezést akarunk lefordítani, fordítási hibát kapunk. Az ilyen esetekben a típus megadása már nem hagyható el, hanem kötelező. Az értelmezőben azért kapjuk a kivételt, mert az alapértelmezés szerint egy adott típus, méghozzá a () típus példányát társítja a read függvényhez. Ezért a fenti esetben valójában a () egyetlen elemét, a () várná és fogadná el az elemzés. GHCi> read "()" () Ha a paraméterként megadott szövegből egy egész számot szeretnénk kinyerni, akkor a típus hozzáadásával a read megfelelő példányát ki tudjuk erre a célra választani. GHCi> read "42" :: Integer 42 Az érdekesség kedvéért megjegyezzük, hogy adódhatnak olyan esetek, amikor a függvény definíciójából nem látszik közvetlenül a benne alkalmazott túlterhelt nevek többértelműsége. Ehhez nézzük most meg az alábbi definíciót: 65
f :: String -> String f = show . read A fordítás során egy ehhez hasonló választ fogunk kapni: Fail.hs:2:5: No instance for (Show a0) arising from a use of ‘show’ The type variable ‘a0’ is ambiguous ... In the first argument of ‘(.)’, namely ‘show’ In the expression: show . read In an equation for ‘f’: f = show . read Fail.hs:2:12: No instance for (Read a0) The type variable ‘a0’ is ... In the second argument of In the expression: show . In an equation for ‘f’: f
arising from a use of ‘read’ ambiguous ‘(.)’, namely ‘read’ read = show . read
Ezt csak úgy tudjuk kiküszöbölni, ha valamilyen módon megadjuk a kompozícióban résztvevő függvények valamelyikének a típusát. Például, ha azt szeretnénk, hogy a bemenetként érkező szöveg logikai értékként legyen értelmezhető, akkor a következő módon kell hozzá módosítanunk az előző programot. f :: String -> String f = show . (read :: String -> Bool)
2.7.5. Átfedő példányok A típusváltozók megjelenésével könnyen előfordulhat, hogy olyan példányokat hozunk létre, amelyek átfednek. Vagyis a megadott példányok közül több is illeszkedik az adott helyzetben alkalmazandó típusra, ezért a fordító nem tudja egyértelműen eldönteni, melyik implementációt kell választania. Ezt a Haskell 98 szabvány úgy igyekszik garantálni, hogy nem engedi a példányok definíciójában a típuskonstruktorok paramétereinek specializálását. Ennek vizsgálatához nézzük meg a C osztály és annak példányának definícióját:
66
class C a where c :: a -> Int instance C [Char] where c _ = 0 Ennek fordításakor a következő hibaüzenetet fogjuk kapni: Illegal instance declaration for ‘C [Char]’ (All instance types must be of the form (T a1 ... an) where a1 ... an are *distinct type variables*, and each type variable appears at most once in the instance head. Use -XFlexibleInstances if you want to disable this.) In the instance declaration for ‘C [Char]’ Ahogy viszont az üzenetben is olvashatjuk, a FlexibleInstances kiterjesztés használatával az ilyen példányok is engedélyezhetőek (B.2. alfejezet). Ennek az a lényege, hogy a példányok fejlécében szereplő paraméteres típusban megköthetjük a típusváltozók értékét. Vagyis ebben az esetben az általános [a] típus helyett a tőle szűkebb [Char] típusra is megadhatjuk a példányt. Bár ezzel a fordító már hajlandó elfogadni a programot, a kiértékelés során azonban ismét bajba kerülhetünk, ha a programunk így folytatódik: instance C [a] where c _ = 1 Ilyenkor ezt történik az értelmezőben a kiértékelés során: GHCi> c "foobar" :2:1: Overlapping instances for C [Char] arising from a use of ‘c’ Matching instances: instance C [a] -- Defined at Overlapping.hs:8:10 instance C [Char] -- Defined at Overlapping.hs:5:10 In the expression: c "foobar" In an equation for ‘it’: it = c "foobar" Ezt próbálja helyreállítani az OverlappingInstances kiterjesztés. Ilyenkor a kiértékelés mindig a legjobban illeszkedő példányt választja, vagyis ebben az esetben már a következő eredményt kapjuk: 67
GHCi> c "foobar" 0 Érdemes viszont hozzátenni, hogy mindezek alkalmazása egyáltalán nem kötelező. Egyszerűen elegendő egy csomagolótípust készítenünk egy származtatott típus, a newtype alkalmazásával. newtype TString = TS [Char] instance C TString where c _ = 0 Ekkor az értelmezőben így tudjuk majd használni: GHCi> c (TS "foobar") 0 Ezzel a módszerrel explicit módon tudjuk irányítani, hogy melyik típusokhoz melyik implementációt rendeljük. Egyedüli szépséghibája a megoldásnak, hogy a csomagolótípus konstruktorát ilyenkor mindig ki kell írnunk. Ezt viszont nagyon gyakran alkalmazzák a gyakorlatban.
2.7.6. Típuskonstruktor-osztályok Eddig nem foglalkoztunk azzal, hogy a típusosztályok fejlécében megadható típusváltozókat miként tudjuk használni a metódusok típusának leírásában. A paraméteres típusok jelenlétében ugyanis nem csak típusok paraméterének helyén jelenhetnek meg a változók. Erra példát láthattunk akkor, amikor az Eq osztály példányát adtuk meg a [] (lista) típusára. Viszont nem árt tudni, hogy más fajtájú, vagyis magasabbrendű típusok helyére is írhatunk változókat és azok felett is paraméterezhetjük így az osztályokat. Például a map, vagyis a leképező függvényt el tudjuk vonatkoztatni a listáktól, és megengedhetjük, hogy lényegében bármelyik típusra tudja működni, amelynek egyetlen paramétere van. Ekkor kapjuk a Functor típuskonstruktor-osztályt és benne az fmap műveletet. class Functor f where fmap :: (a -> b) -> f a -> f b Itt tehát láthatjuk, hogy az f típusváltozó kap paramétereket, vagyis a map eredeti típusában a listát váltja le. Ezért amikor megadnunk neki egy példányt, akkor bármelyik, azzal azonos fajtájú típust beírhatjuk a helyére. Ha engedélyezzük a KindSignatures kiterjesztést (B.2. alfejezet), akkor ezt az osztályt szemléletesebben az alábbi módon is fogalmazhatjuk. 68
class Functor (f :: * -> *) where fmap :: (a -> b) -> f a -> f b Ebben az esetben kiemeltük, hogy az f fajtája * -> *, csak ilyen típusokra példányosítható. Maga a lista is ilyen, ezért ha megadjuk arra a példányt, akkor az lényegében a map függvény lesz. instance Functor [] where -- map :: (a -> b) -> [a] -> [b] fmap = map Elsőre talán kicsit furcsának tűnik, de a [a] típust lehet úgy is írni, hogy [] a. A példány megadásakor a hozzá tartozó típusváltozót már nem kell megadni, mivel azt a metódusok definíciójában töltjük majd ki. Természetesen ez sok más, egyparaméteres típusra is megadható. Például vehetjük a kétágú bináris fákat ábrázoló Tree típust: data Tree a = Leaf | Node a (Tree a) (Tree a) A neki megfelelő példány a következő lesz: instance Functor Tree where -- fmap :: (a -> b) -> Tree a -> Tree b fmap _ Leaf = Leaf fmap f (Node x lt rt) = Node (f x) (fmap f lt) (fmap f rt)
2.8. Összefoglalás Ebben a fejezetben megismerhettük, hogy a tisztán funkcionális nyelvekben mit jelent a szigorú és statikus típusozás, mi a típusok fajtái. Továbbá láthattuk, milyen módon tudjuk mi magunk is ezen nyelvek típusait a sajátjainkkal bővíteni. Szükség esetén egyszerűen csak adhatunk másik nevet egy típusnak vagy típuskompozíciónak, de akár mi magunk is képesek vagyunk mind a típus elemeinek ábrázolását, illetve a típushoz társított műveleteket meghatározni. Ez utóbbira egy nagyon erős, más nyelvekben nem annyira elérhető módszert kínálnak fel ezek a nyelvek, az algebrai adattípusokat. Mellette szerepeltek még a típusosztályok, amelyek segítségével neveket lehet programjainkban túlterhelni és attól függően kiválasztani a hozzájuk tartozó viselkedést, hogy milyen típussal alkalmazzuk.
69
A. függelék Magyar-angol szótár A funkcionális programozáshoz nem kötődik szélesebb körben elterjedt magyar terminológia. Ezért az alábbi táblázatban szeretnénk összefoglalni a jegyzetben gyakran alkalmazott, de esetleg kevésbé közismert szakkifejezések, rövidítések eredeti angol megfelelőjét. adatkonstruktor akció algebrai adattípus alkalmazás (függvény) azonosító ág csomagolótípus deklaratív programozás Descartes-szorzat diszjunkt unió egyszeri értékadás egységelem értelmezési tartomány (függvény) értékkészlet (függvény) eseti polimorfizmus fajta (típus) fej (lista) fejléc (típusosztály) felsorolásos típus fordítási hiba futási hiba futtató rendszer függvény 70
data constructor action algebraic data type (ADT) application identifier branch wrapper type declarative programming Cartesian product disjoint union single assignment identity element domain range ad hoc polimorphism kind head head enumerated type compile-time error run-time error run-time system function
hajtogatás halmazkifejezés hatókör (név) hivatkozási helyfüggetlenség joker minta kiszámíthatóság kivétel kompozíció (függvény) konkatenáció kötés körrizés kötési erősség kötési irány kötött (változó) kvantor lista lokális definíció lusta (kiértékelés) magasabbrendű függvény margószabály megszorítás (típus) mellékhatás metódus minimális definíció (típusosztály) minta mintaillesztés mohó (kiértékelés) monomorfizmus nevesített típus néma (programozás) névtelen változó nyelvi ízesítés őrfeltétel parametrikus polimorfizmus paramétermentes (programozás) parciális függvény polimorfizmus principális típus rekurzió részleges függvényalkalmazás start kifejezés 71
folding list expression scope referential transparency wildcard pattern computability exception composition concatenation bind(ing) currying precedence associativity bound (variable) quantifier list local definition lazy (evaluation) higher-order function off-side rule context side effect method minimal complete base pattern pattern matching strict (evaluation) monomorphism type synonym tacit (programming) anonymous variable syntax sugar guard (expression) parametric polimorphism point-free (programming) partial function polimorphism principal type recursion partial function application start expression
statikus típusos szabad (változó) számítás származtatott típus szelet (függvény) szigorúan típusos tiszta tisztán funkcionális típus típusellenőrzés típuskikövetkeztetés típuskonstruktor típuskonstruktor-osztály típusleírás típusmegkötés típusosztály típusosztály-példány típusrendszer típusváltozó totális függvény tördelés törzs (függvény) törzs (lista) túlterhelés ügyes konstruktor véges lista végtelen lista
staticly typed free (variable) computation derived type section strongly typed pure purely functional type type checking type inference type constructor type constructor class type declaration (type) coercion type class type class instance type system type variable total function indentation body tail overloading smart constructor finite list infinite list
72
B. függelék A Glasgow Haskell Compiler A jegyzetben leginkább a Glasgow Haskell Compilerre (GHC) mint a Haskell nyelv de facto szabványára, pontosabban annak a Haskell Platformban fellelhető változatára támaszkodunk. Ez letölthető a Haskell honlapjáról, a legtöbb operációs rendszerre és architektúrára egyszerűen telepíthető: http://www.haskell.org/platform/ Ebben a függelékben szeretnénk összefoglalni a Haskell Platform és a GHC sajátosságait, a használatukhoz kapcsolódó megfontolásokat.
B.1. Haskell Platform A Haskell Platform nevű disztribúció tartalmazza a Haskell nyelven történő programfejlesztéshez alapvető eszközöket, kiterjesztéseket, valamint a cabal-install csomagkezelőt. Ez utóbbi segítségével többezer további kiegészítőt, függvénykönyvtárat tudunk telepíteni egy központi adatbázisból, a HackageDB-ből. Ez a következő címen érhető el: http://hackage.haskell.org/ Innen a legfrissebb csomaglistát mindig a következő paranccsal tudjuk letölteni: $ cabal update Egy adott csomagot ("hackage") pedig így lehet telepíteni: $ cabal install Az aktuálisan telepített csomagok listáját a ghc-pkg parancs tudja megmutatni: $ ghc-pkg list 73
B.2. Nyelvi kiterjesztések A GHC a Haskell 98 szabványon túl számos kiegészítést tartalmaz, lényegében állandó kísérletezgetések színtere. Ezek közül néhány egészen stabil és megbízható, néhányat viszont csak nagyon különleges esetekben javasolt engedélyezni. Ezért a GHC alapértelmezésben csak nagyon kevés kiterjesztést tesz elérhetővé, a használatukat külön engedélyezni kell.
B.2.1. A kiterjesztések engedélyezése és tiltása Kiterjesztéseket a következőképpen tudunk engedélyezni: – A forráskód elejére beillesztünk egy LANGUAGE pragmát, egy speciális kommentet, amelyet a fordító képes értelmezni. A pragma után meg kell neveznünk a bekapcsolni kívánt kiterjesztést. {-# LANGUAGE #-} Ilyen utasításokat {-# és #-} jelek közé szúrva tudunk kiadni. Egyetlen LANGUAGE pragma után akár egyszerre több kiterjesztést is felsorolhatunk, habár karbantarthatósági okokból ezt nem túl gyakran alkalmazzák. {-# LANGUAGE , , ... #-} A fordítás során, a parancssorban is hivatkozhatunk az adott kiterjesztés nevére a -X paraméterrel. Itt az -X kapcsoló után adhatjuk meg az alkalmazandó kiterjesztés nevét. – Az értelmezőben a :set paranccsal is be- és kikapcsolhatunk kiterjesztéseket: GHCi> :set -X GHCi> :set -XNo Kiterjesztéseket kikapcsolni az :unset parancs segítségével is tudunk: GHCi> :unset -X
74
Az aktuálisan érvényes nyelvi beállításokat a paraméterek nélkül :set parancs kiadásával érhetjük el. Például GHC 7.10.3 esetében ezek a következők: GHCi> :set options currently set: none. base language is: Haskell2010 with the following modifiers: -XNoDatatypeContexts -XNondecreasingIndentation -XTypeSynonymInstances GHCi-specific dynamic flag settings: other dynamic, non-language, flag settings: -fimplicit-import-qualified warning settings:
B.2.2. A jegyezetben alkalmazott kiterjesztések A GHC kiterjesztéseinek listája verziónként folyamatosan változik, ezért azok teljes listáját itt nem közöljük. Ezek közül csak azok szerepelnek összefoglalásként, amelyeket a jegyzetben alkalmaztunk. A GHC aktuális változata által támogatott kiterjesztéseket a --supported-extensions kapcsolóval lehet lekérdezni. A kiterjesztésekről bővebben a User’s Manualban lehet olvasni. Kiterjesztés EmptyDataDecls FlexibleInstances
Viselkedés Megadhatóak olyan algebrai típusok is, amelynek nincs egyetlen konstruktora sem. A típusosztályokat szabad típusok tetszőlegesen egymásba ágyazott kompozíciójára példányosítani. A definíciókban a típusváltozókhoz megadható a fajtájuk. A típusosztályoknak nem csak egyetlen típusváltozója lehet. Egy típusosztály esetében több illeszkedő példánynál a leginkább illeszkedőt választjuk.
