☰ Menu

Scene.hu

Magyar demoscene portál – grafikusok, zenészek, programozók alkotói közössége

Haskell_Logo_w.pngNé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.

vagas.png
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:

data Tree a = Leaf a
            | Node (Tree a) a (Tree a)

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:

type SearchTree k v = Tree (k,v)

(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:

lookup :: Ord k => k -> SearchTree k v -> Maybe v
lookup key (Node left (k,v) right) =
  case (compare key k) of
    LT -> lookup key left
    GT -> lookup key right
    EQ -> Just v
lookup key (Leaf (k,v)) =
  if k==key
    then Just v
    else Nothing

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:

class Eq a => Ord a where
  compare :: a -> a -> Ordering
  …

data Ordering = LT | EQ | GT

(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):

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  — ez utóbbi a “nemegyenlő” operátor
  — a dupla kötőjel pedig az (egysoros) commenteket jelzi

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!):

data Maybe a = Just a
             | Nothing

instance Eq a => Eq (Maybe a) where
  Just x  == Just y   =  x == y
  Nothing == Nothing  =  True
  Just _  == Nothing  =  False
  Nothing == Just _   =  False

(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:

safeDiv :: Fractional a => a -> a -> Maybe a
safeDiv x y =
  if y==0
    then Nothing
    else Just (x/y)

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:

egy   :: Type1 -> Maybe Type2
ketto :: Type2 -> Maybe Type3
harom :: Type3 -> Maybe Type4

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:

szamitas :: Type1 -> Maybe Type4
szamitas x = return x >>= egy >>= ketto >>= harom

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

szamitas x = do
  y <- egy x
  z <- ketto y
  w <- harom z
  return w

Í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 :)

class Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  return :: a -> m a

instance Monad Maybe where
  Just x   >>=  f  =  f x
  Nothing  >>=  _  =  Nothing
  return x = Just x

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…

Categories: Programozás | Tags

23 Responses so far.

  1. avatar Jimmi says:

    Az még érdekelne, hogy teljesítményben ez hogyan viszonyul mondjuk a Python / Java / C++ nyelvek implementációihoz.

  2. avatar Charlie says:

    Birom a writeonly usereket Jimmy. Bar ez konkretan nem az, de lehet kovetkezteni a forditott kod (es a cucchoz adott rutinkonyvtarak) altalanos sebessegere.

  3. avatar Jimmi says:

    Charly: köszi szépen. De most miért is voltam writeonly?

  4. avatar Charlie says:

    Mert ezt mar valamelyik korabbi Haskell threadbe is belinkeltem. :)

  5. avatar Jimmi says:

    Én kérek elnézést :)

  6. avatar blala says:

    Na, sebessegben a kovetkezo a helyzet (mondjuk a GHC compilert nezzuk, ma az a leggyorsabb, de ezeket eleg aktivan fejlesztik), mar amennyire en ertem. A laziness mint feature ad valamekkora overhead-et, de ez annyira nem jelentos szerintem, tizenszazalekokra tippelnem. A garbage collector is ad overhead-et, ami eleg jelentos is lehet akar, ilyenkor el kell gondolkozni hogy jol van-e felepitve a program (lasd meg lejjebb). A python-nal szerintem jelentosen gyorsabb a GHC altal forditott kod. Egy *jol megirt* c++ programnal altalaban lassabb, mondjuk 2x (egy *jol megirt* haskell valtozat) – edit: na jo, ez lehet hogy tulzas. A 2x helyere egy nagyobb szamot is gondalhatunk. De azert nem 10x :) –, kiveve ha pl sok threadunk van mert akkor durvan leveri (lightweight thread-ek vannak, mivel nincs state kurvagyorsan lehet valtogatni koztuk). A java-rol fingom sincs. Amugy kurvara azon mulik hogy milyen algoritmusokat hasznal az ember. Azt tudni kell, hogy ezek a pure functional nyelvek egeszen mas algoritmusokat illetve adatstrukutrakat szeretnek mint a megszokott imperativ nyelvek, es vica versa. De megfelelo algoritmus/adatstruktura kombinacioval szerintem aszimpotikusan ugyanolyan sebessegeket lehet elerni mint mondjuk C++-ban. Pl a Haskell standard libraryban vannak grafalgoritmusok, amik teljesen mashogy reprezentaljak a grafokat mint mondjuk a Boost library vagy a tobbi megszokott library, inkabb az elozo reszben szereplo listakhoz hasonloan; de maguk az algoritmusok azt hiszem nem lassabbak mint az imperativ megfelelojuk.

    Charlie linkjehez pedig azt fuznem mostmar akkor hozza (mar a multkor is akartam), hogy ezt irta az emlitett benchmark aktualis szervezoje a temaban
    [ módosítva Oct.25. 14:54 ]

  7. avatar blala says:

    Szoval, a Haskell valoban nem valo mindekinek. Egy karakter elteres a kod kozepen (mondjuk foldl vs foldr) konnyen okozhat 100x-os sebessegkulobseget. Ha gyors kodot akar az ember, nem art ha tudja mit csinal :)

  8. avatar pezia says:

    A tobbeseket n-eseknek soktak mondani, nem?

  9. avatar blala says:

    lehet :) matematikaban hasznaljak a tobbesek szot is, de itt eleg hulyen nezett ki.

  10. avatar pohar says:

    # Közkívánatra: Mi az Haskell, és miért jó? (harmadik rész)
    # Közkívánatra: Mi az Haskell és miért jó? (második rész)
    # Közkívánatra: Mi az Haskell, és miért jó? (első rész)

    a második rész címében nem volt vessző. ennek van valami jelentősége, amit sok C-ben programozó PC-s nem érthet? :)

  11. avatar blala says:

    a lektor figyelme oszcillal?

  12. avatar slyspy says:

    440Hz-cel.

  13. avatar Gargaj says:

    azer remelem a befejezo reszben kiderul hogy miert jo… meg hogy miert kozkivanatra… :D

  14. avatar blala says:

    Kozkivanatra azert mert legalabb egy valaki kerte valahol ezen az oldalon hogy legyen, vagy kerdezte, vagy valami ilyesmi :) Azt hogy miert jo, azt akkor most nem lonem le :D Vagy esetleg, idozitsem a demot is a befejezo reszhez, es akkor senki nem fog rakerdezni hogy miert jo? :DD

    (szoval tovabbra is azert jo, mert viszonylag konnyen lehet – es egyaltalan lehet – bugmentes, de legalabbis nagysagrendekkel kevesebb bugot tartalmazo programot irni benne, kulonosen igaz ez ha tobb mint 1 threadunk van; es raadasul meg jobb kedve is van a programozonak kozben. Konnyebb a letezo kod ujrafelhasznalasa, konnyebb modularisan felepiteni a programokat. Arrol nem is beszelve hogy szerintem a szintaxisa is sokkal jobb mint a c/java iskolanak, de ez eleg szubjektiv persze)

  15. avatar pohar says:

    lehet, hogy így kerülne a helyére az a fránya vessző a címben:

    Miért, jó a Haskell?

  16. avatar blala says:

    na. fixed for you. (hihetetlen hogy mindenki ezen viccelodik, pedig tenyleg jo am, nem szatirat irok :)

  17. avatar slyspy says:

    Ma spamet kaptam Haskel Huxfordtól.

  18. avatar pontscho says:

    Kozkivanatra azert mert legalabb egy valaki kerte valahol ezen az oldalon hogy legyen, vagy kerdezte, vagy valami ilyesmi :)

    En voltam en voltam!

  19. avatar blala says:

    es meg mindig erdekel? :)

  20. avatar Murphy says:

    Engem pl. egyre jobban érdekel! ;)

  21. avatar pontscho says:

    Siman. Kelloen elborult meg mindig. :)

  22. avatar blala says:

    Aki meg mindig olvassa ezt a sorozatot, az esetleg mondhatna valami konstruktiv kritikat arrol hogy mi jo, mi nem jo, mi ertheto, mi nem (tudom, az hogy miert jo :), merthogy igy elegge vakon irom a cikkeket, nem tudom ki a celkozonseg…

  23. avatar FooLman says:

    Celkozonseg, jelentkezem!

    Amit meg ilyen eltompult aggyal szivesen latnek, valami konkret dolog haskellben. Mert ertem en, hogy binaris fa, meg ertem en, hogy faktorialis, meg alapvetoen tetszik is az egesz, csak valahogy nem all ossze a dolog valami hasznossa elsore. Bar mondjuk amilyen utemben mostanaban hulyulok, csoda, hogy el tudtam olvasni a betuket…
    Amugy jok a cikkek, meg olvasmanyosak, ugyhogy hajra tovabb! :)

Leave a Reply

You must be logged in to post a comment.

Ugrás a lap tetejére Ugrás a lap aljára