Scene.hu

Népművelő sorozatunk harmadik epizódjához érkeztünk, lehetne akár az is a címe, hogy “3 cikk egy témában”… Ma lesz keresőfa, és ennek kapcsán type classes, a Maybe, és egy röpke pillanatra megvillanak a monádok is… Amennyiben valaki frissíteni szeretné az emlékeit, az első rész itt olvasható, a második pedig itt.

Az előző rész végén található bináris fás példát a figyelmes olvasónak már értenie kell(ene), így azt nem is magyaráznám sokat; talán csak annyit tennék hozzá, hogy a ++ operátor listák összefűzésére való, és hogy azért nem kellenek zárójelek, mert a függvény-applikáció magasabb precedenciával bír, mint a ++ (vagy mint bármely más operátor).

De hogy kicsit még a bináris fáknál maradjunk, ezeknek egy tipikus alkalmazása a bináris keresőfa: ha (key,value) – magyarul (kulcs,érték) – párjaink vannak, és a kulcsok halmazán adott egy rendezés, akkor tárolhatjuk őket egy (ideális esetben kiegyensúlyozott) bináris fában, úgy, hogy a baloldali ágakon a kulcs értéke mindig kisebb, mint a jobboldali ágakon. Ennek előnye például, hogy log(n) időben tudunk keresni kulcs alapján. Lássuk hogy néz ez ki Haskellben.

Először is, ehhez kicsit másfajta fa kell, olyan, ahol az elágazásokban is ülnek értékek (na, ki csinálta meg a házi feladatot? :); úgyhogy újradefiniáljuk a fa típust:

Majd definiáljuk a keresőfa típust, ami ezúttal két típussal is parametrizálva van, mégpedig a kulcsok és értékek típusaival:

(a type kulcsszóval típus-szinonímákat vezethetünk be; az (x,y,z,…) alakú kifejezések pedig párok, hármasok, és általában tuple-ök – ez hogy van magyarul? a “többesek” elég hülyén hangzik, más meg nem jut eszembe). Végül lássuk a keresést megvalósító függvényt; itt jönnek az izgalmak:

Itt hirtelen sok újdonság megjelent, lássuk őket szépen sorban. Először is a Python nyelvhez hasonlóan a Haskell is layout-based, azaz az egymásba ágyazott kód-blokkokat egyszerűen indentálással jelölhetjük (ez titokban már felbukkant a típusdeklarációknál, amiket egy sorba is írhattam volna, de így talán könnyebb olvasni). Szerencsére a kapcsos-zárójelek (“bajusz”) és pontosvesszők szerelmeseinek sem kell aggódniuk, az a stílus is működik; sőt, a kettőt szabadon keverhetjük!

Az első sorban rögtön két furcsa dolog is megjelent (három, ha azt is beleszámoljuk, hogy nem csak az a, b és c betűkkel lehet típusváltozókat jelölni :). Az Ord k => arra utal, hogy a k típustól (ami a kulcsok típusa, k mint key) elvárjuk, hogy össze lehessen hasonlítani az értékeit. Az Ord (az angol ordered szóból) egy type class (típusosztály); ez kicsit olyasmi, mint az objektumorientált nyelvekben az osztályok, de azért nem pont arról van szó. Ez egyébként egy olyan aspektusa a Haskell nyelvnek, ami más “mainstream” nyelvekben nem igazán található meg (na jó, ez vicc volt, természetesen a Haskell nem éppen mainstream; arra gondoltam, hogy azon nyelvek körében, amelyek legalább annyira elterjedtek, mint a Haskell, feltehetőleg nem találjuk meg ezt a fícsört). Az Ord definíciója valahogy így néz ki:

(itt a … helyén még definiálva vannak a >, <, >=, <= operátorok, és a min, max, függvények; de ezeket mind lehet a compare segítségével definiálni, és vica versa). Látszik, hogy már maga az Ord is ráépül egy másik osztályra, az Eq-re, amely az egyenlő/nemegyenlő fogalmat absztrahálja (az angol equal szóból):

Tehát ha egy függvény típusába beleírjuk az Eq a => kontextust, akkor onnantól használhatjuk az == operátort a típusú elemek összehasonlítására (ha meg nem írjuk oda, de használjuk, akkor a compiler kitalálja és “odaírja” magától, természetesen). A típusosztályokat eredetileg az overloading problémájának megoldására találták ki, de azóta kiderült, hogy elég jól belenyúltak a tutiba :).

Egy konkrét típust deklarálhatunk az osztály tagjának, itt van mondjuk rögtön a Maybe a, amit deklarálhatunk például az Eq osztály tagjának (feltéve, hogy a kiinduló a típus már tagja volt!):

(ezt a nem túl izgalmas feladatot egyébként a compiler elvégzi helyettünk, ha szépen megkérjük: mindössze a deriving Eq szavakat kell a definíció végére illeszteni). A Maybe a-t az Ord osztály tagjának deklarálni viszont nem lenne sok értelme, hacsak nem akarjuk expliciten hogy a Nothing mindenkinél kisebb legyen, például.

Visszatérve a lookup függvényünkre, most már nagyjából érhetőnek kellene lennie; annyit még megjegyeznék, hogy az if / then / else és a case / of kifejezések, azaz mindig értéket adnak vissza (if / then nincs is else nélkül!).

Inkább a Maybe-ről ejtenék még pár szót. Mint az a fenti definícióból könnyen kitalálható, ez arra való, hogy egy feladat esetleges sikertelenségét biztonságosan elkódoljuk (a keresés példában azért használtuk, mert elképzelhető, hogy a kulcs, amire kerestünk nem létezik; viszont ebben az esetben is illik visszaadni valamilyen értéket). Egy másik, banálisan egyszerű példa a nullával való osztás elkerülése:

Imperatív nyelvekben ezt gyakran valamilyen flaggel, vagy nem használt értékkel (pl. -1) oldják meg; ez kicsit ugyan elegánsabb, de ha csak ennyiről lenne szó, nem lenne érdemes több szót vesztegetni rá.

De a Maybe nem csak egy ártatlan típuskonstruktor, nem ám! A Maybe titokban egy monád… (ezen a ponton szoktak a sárkány legyőzésére induló bátor vitézek először megtorpanni… úgyhogy kitartás, kedves Olvasó!). A monád szó a kategóriaelméletből került át a programozók szótárába, de szerencsére mi most ezen nem fogunk aggódni, mintegy kihúzva ezzel a sárkány méregfogát :).

A monád egy olyan struktúra, ami lehetőve teszi műveletek sorrendjének deklarálását (ezen a ponton felhívnám a figyelmet, hogy Haskellben az “utasítások” végrehajtásának sorrendje nem definiált: azt a compiler saját hatáskörében dönti el…). Tegyük fel, hogy egy számítás több kisebb lépésből áll össze – ezt egészen realisztikus feltevésnek érzi a szerző :) -, és mindegyik elszállhat valamilyen hibával (mint pl. a lookup fent). Ahelyett azonban, hogy azonnal holmi exceptionökhöz nyúlnánk – bár tehetnénk -, az egyes lépéseket elkódolhatjuk mint a -> Maybe b típusú függvények, például:

Ezekből szeretnénk egy szamitas :: Type1 -> Maybe Type4 típusú függvényt összekombinálni valahogy, és azt várjuk el, hogy bármelyik ponton is történik valami hiba, Nothing-ot kapjunk vissza, ha pedig nem történik hiba, akkor (Just) a végeredményt. Nos, pontosan erre jó a monád! A szamitas függvényünk így fog kinézni:

avagy, kissé emberbarátibb szintaxissal, de pontosan ugyanez:

Így már rögtön nem is olyan ijesztő, ugye? További mellébeszélések helyett (na meg, mert ez a rész már nagyon hosszúra nyúlt), leírom inkább a monád definícióját (majdnem…), illetve hogy a Maybe hogyan monád; jövő hétig lehet nézegetni/gondolkodni :)

Az érdeklődést fenntartandó (muhaha), még gyorsan megjegyzem, hogy a monádok teszik lehetővé az input/output-ot is, amiről talán majd legközelebb írok bővebben is…