☰ Menu

Scene.hu

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

Haskell_Logo_w.pngVégre, végre, itt a negyedik rész, csak itt, csak most, csak önöknek, 150%-al több kódrészlettel!

Komolyabbra fordítva a szót, többen konkrét példákat kértek rajtam számon; úgyhogy gondoltam is, hogy akkor a mai részben ilyenek lesznek (bár szerintem az eddigiek is azok voltak). De aztán meggondoltam magam (ördögi kacaj), és főleg az IO monádra fogok koncentrálni (még ördögibb kacaj :)… Mindenesetre a copy/paste-el csak óvatosan – a szerző is megjárta már ezzel -, ugyanis a weboldalról másolt kódrészletek, bár első ránézésre jónak tűnhetnek, a sortörés karaktereket nem feltétlenül a rendszer natív formájában tartalmazzák, ami a compilert könnyen meggátolhatja a rendeltetésszerű működésben… (nyilván ez rendszer- és böngészőfüggő).

Jó hír viszont, hogy múlt szombaton kijött a GHC compiler legújabb, 6.8.1-es változata (a számozásból naívan levonhtató következtetésekkel ellentétben ez egy major release, az utolsó hasonló a 6.6.1 volt, áprilisban, előtte pedig a 6.6, tavaly októberben).

Az előző részek itt találhatóak: első, második, harmadik.

vagas.png
Vágjunk akkor bele!

module Peldaul where

Így kezdődik egy Haskell program, mely első sorban megmondjuk az adott module nevét (ami mindig nagybetűvel kezdődik, hasonlóan a típusokhoz, adatkonstruktorokhoz, és típusosztályokhoz, és ellentétben a függvényekkel, argumentumokkal és típusváltozókkal, melyek kisbetűvel kezdődnek). Amíg ilyen kis egyszerű egyfile-os programokról van szó, ez nem igazán számít, egyébként viszont elvárják az embertől, hogy a filenév és a module neve stimmeljen, library-k esetén legalábbis; illetve ha futtatható programot szeretnénk, akkor a module neve legyen Main, és legyen egy main :: IO () típusú “függvény” (pont mint C-ben a void main() { … }). Bery egy hónappal korábbi kérdésére válaszolva :), a module-nak a file végén van vége, tehát 1 file = 1 module.

import Data.List

Ez után beimportálhatjuk a namespace-be a library-k közül azokat amiket használni szeretnénk (a linkre kattintva a GHC standard library-k dokumentációját találjuk). Van egy alapértelmezett készlet, az ún. Prelude, amit mindig beimportál nekünk a compiler, kivéve ha szólunk neki hogy ne tegye. Egyébként a többi importálást is lehet finomhangolni, expliciten megmondva hogy melyik függvényt szeretnénk illetve melyiket nem.

És már írhatjuk is a kódot! Innentől a dolgok sorrendje nem számít. Kezdjük mondjuk egy egyszerű, sőt, egyenesen naív, ámde annál rövidebb quicksort implementációval:

qsort :: Ord a => [a] -> [a]
qsort (x:xs) = qsort a ++ [x] ++ qsort b
  where (a,b) = partition (<x) xs
qsort [] = []

A legtöbb Haskell compilernek/interpreternek van REPL, azaz Read-Eval-Print Loop funkcionalitása, amiben interaktívan ki is tudjuk próbálni a kódot. A GHCi nevűt használva ez valahogy így néz ki:

Prelude> :l Peldaul.hs
[1 of 1] Compiling Peldaul       ( Peldaul.hs, interpreted )
Ok, modules loaded: Peldaul.
*Peldaul> qsort [7,1,4,5,2,13,21,4,5,4,17]
[1,2,4,4,4,5,5,7,13,17,21]
*Peldaul>

Látszólag működik…

Kis magyarázat a kódhoz: a partition nevű függvény, ami a Data.List library része, típusa pedig (a -> Bool) -> [a] -> ([a],[a]), szóval ez azt csinálja, hogy az első paraméterként kapott függvényt használva szétbontja a második paraméterként kapott listát két részre, és ezeket egy párként adja vissza. Vegyük észre, hogy bár a “listák párja” az egy darab objektum, de a pattern matching segítségével ingyen megkapjuk azt a fícsört, mintha több visszatérési értéke is lehetne egy függvénynek (Charlie, figyelsz? :) A (<x) pedig az a függvény, amit így is lehetne definiálni: (<x) y = y < x.

Hogy egy egészen igazi programot is lássunk, kimenettel, bemenettel és rózsaszín mignonnal, álljon itt egy program(ocska), mely megszámolja a standard input-on érkező szövegben a szavakat (lásd még a unix wc parancsot, mint “word count”).

module Main where

main = do
  interact $ show . length . words
  putChar ‘\n’  — egy újsor karaktert is kirakunk a végére

(megjegyzem, elég sok más unix parancsot is lehet egysoros Haskell programokként implementálni :). Az interact függvény egyetlen paramétere egy (String -> String) típusú függvény, kimenete pedig egy IO action:

interact :: (String -> String) -> IO ()

mely azt csinálja, hogy a standard inputra érkező adatra ráengedi ezt a függvényt, a végeredményt pedig kitolja a standard outputra. A $ karakter a függvény-applikáció operátor: f $ x = f x. Ennek látszólag nem sok értelme van, azonban nagyon alacsony a precedenciája, így sokszor meg lehet szabadulni zárójelhalmazoktól a segítségével. Tehát írhattam volna azt is, hogy interact (show.length.words), a kettő teljesen ekvivalens. A . operátor pedig a függvény-kompozíció operátor: (f.g) x = f (g x); típusa (.) :: (b -> c) -> (a -> b) -> a -> c. Matematikában ezt kis karikával szokták jelölni, de olyan nincs az ASCII karakterkészletben (bár Haskellben elvileg használhatunk Unicode operátorokat is, a standard library-ben nincsenek ilyenek jelenleg). (Érdekesség, hogy első ránézésre teljesen önellentmondó módon, ezt a programozási stílust, amikor függvény-kompozíciókkal operálnak explicit paraméterek helyett, “point-free style”-nak hívják :). A feloldás ott van, hogy a “point” itt nem a . operátorra utal, hanem… valami egész másra, ami a matematika mély bugyraiban található. Itt kicsit elbizonytalanodtam, mert a hirtelen talált egyetlen referencia szerint egész másra utal (bónuszként az viszont a matematika még mélyebb bugyraiban leledzik), mint azt én gondoltam eddig :). Végül, a words szavak listájára bont egy string-et, a length megmondja egy lista hosszát, a show pedig stringgé alakít egy objektumot, jelen esetben egy számot.

Azt hiszem, pár szót kellene szólnom erről a misztikus IO típuskonstruktorról. A korábbiakkal ellentétben ennek nincs definíciója, hanem a fordítóba van beépítve; ebből a szempontból speciális, ámde minden más szempontból úgy viselkedik, mint bármely más típuskonstruktor. Az IO a típus egy olyan, esetleges side-effectekkel bíró actiont reprezentál, mely végeredményként egy a típusú értéket ad vissza. Pedagógiailag képzelhetjük azt, hogy ez a definíció:

data IO a = IO (World -> (World,a))

ahol egy misztikus World típus reprezentálja a világ állapotát, amitől az IO action függhet, illetve azt megváltoztathatja. Emlékezzünk rá, hogy a Haskell egy pure nyelv: a függvényeknek nincs megengedve, hogy megváltoztassák a világ állapotát, sőt, az sem, hogy az befolyásolja az eredményüket! Talán segít a megértésben a következő két sor:

getChar :: IO Char
putChar :: Char -> IO ()

Itt a () az úgynevezett Unit típust jelöli: ennek egyetlen értéke van, amit szintén ()-al jelölnek (ez sajnos nem teljesen igaz, mert a nyelv lazy; de a mi szempontunkból megfelelő definíció). Tehát az IO () az egy olyan IO action, ami nem ad vissza semmit (legalábbis semmi érdekeset).

A fenti pedagógiai definícióval élve, az IO is egy monád, mégpedig a következő módon:

instance Monad IO where
  return x   =  IO (\world -> (world,x))
  act >>= u  =  IO act’ where
    act’ world = g world’ where
      IO f = act
      (world’,y) = f world
      IO g = u y

Aki ezt érti, az lényegében érti az IO-t a Haskellben :). Sajnos ez most kicsit komplikált lett, de hát such is life, mondaná az angol… A lényeg, hogy a World -> (World,a) típusú függvényeket értelemszerűen fűzzük össze (emlékezzünk, hogy >>= operátor típusa Monad m => m a -> (a -> m b) -> m b). Azt azért még elmondom, hogy a \ karakter segítségével anonim függvényeket vezethetünk be, például

add = \x y -> x+y

> add 5 6
11

Ez gyakran nagyon hasznos és/vagy kényelmes. Egyébként azért pont backslash, mert ezt klasszikusan a lambda görög betűvel, mint λ, jelölik a logikusok; viszont olyan nincs az ASCII-ban, és még ez “hasonlít” a legjobban.

Na a lényeg talán kicsit elveszett menetközben: Az IO actionök pont ugyanolyan objektumok, mint bármi más a nyelvben, tehát átadhatjuk őket paraméterként, listákat építhetünk belőlük, vagy akár bináris fákat, vagy bármi mást!

Például, ha van egy listánk a -> IO a típusú függvényekből (amit úgy is képzelhetünk, hogy egy IO action, melynek bemenete és kimenete is egy a típusú) akkor szépen sorban összefűzhetjük őket:

felfuz :: Monad m => [a -> m a] -> (a -> m a)
felfuz [] = return
felfuz (act:rest) = \x -> do
  y <- act x
  felfuz rest y

Ráadásul ez automatikusan működni fog minden monádra, nemcsak az IO-ra. Ha például a múltkori cikk végén levő Maybe-s példában olyan részfeladatokat akartunk volna összefűzni, amelyek egy fix tipusú adatot dolgoznak fel, mondjuk stringeket, akkor ezzel a friss és ropogós függvénnyel is tehettük volna.

Ehhez hasonló módon igen egyszerű új control flow primitívek létrehozása. Triviális példák:

nop :: Monad m => m ()
nop = return ()

forever :: Monad m => m a -> m ()
forever action = do
  action
  forever action

while :: Monad m => m Bool -> m () -> m ()
while cond action = do
  b <- cond
  if b
    then do { action ; while cond action }
    else return ()

És egy nemtriviális példa (amely az előzőekre is épít):

import Control.Concurrent
import System.Time

ct2ms :: ClockTime -> Integer  — milisecundumokká alakítjuk
ct2ms (TOD secs picosecs) = 1000*secs + picosecs `div` (10^9)

diffTime t1 t2 = ct2ms t1 – ct2ms t2

timeout :: Integer -> IO a -> IO (Maybe a)
timeout milisecs action = do
  mv <- newEmptyMVar
  start <- getClockTime
  id <- forkIO $ do { x <- action ; putMVar mv x }

  let cond = do
    { time <- getClockTime
    ; let diff = diffTime time start
    ; return $ diff < milisecs
    }

  while cond (threadDelay 1000)  — egy-egy milisec-et várunk
  res <- tryTakeMVar mv
  case res of
    Just a  -> nop
    Nothing -> killThread id
  return res

Ez azt csinálja, hogy egy IO actionből egy timeout-tal rendelkező IO actiont csinál: ha adott időn belül lefut a cucc, akkor visszakapjuk (Just) a választ, ha nem, akkor abort, és Nothing-ot kapunk visssza. (Egy fejletteb verziója ennek a szolgáltatásnak egyébként belekerült a standard library-be is a bevezetőben említett új GHC-ban). Ha peldául van egy hipotetikus getDataFromTheNet :: IO Stuff actionünk, akkor így (is) használhatjuk a fenti kódot:

almafa = do
  stuff <- timeout (10^4) getDataFromTheNet
  case stuff of
    Just x  -> print x
    Nothing -> putStrLn “Request timed out after 10 secs”

Ebben a timeout-os kódrészletben megint sok újdonság bukkan fel; legérdekesebb talán az MVar. Ezek szinkronizáló változók, többek közt párhuzamosan futó threadek közti kommunikációra lehet őket használni. Működésük nagyon egyszerű: vagy üresek, vagy valamilyen érték van bennük. Egy thread kiveheti egy ilyenből az értékét (takeMVar), és akkor üres lesz; de ha eleve üres volt, akkor a thread várakozik addig, amíg teli nem lesz. Hasonlóan, egy üres MVar-ba bele lehet tenni valamilyen értéket (putMVar), de ha nem volt üres, akkor várunk. A runtime garantálja nekünk, hogy ezek atomi műveletek, nem történhet meg hogy az egyik thread pont akkor kezd el írni, amikor a másik épp valami olvasás közepén van. További érdekesség, de roppant hasznos, hogy a compiler/runtime néha ki tudja analizálni a deadlockokat, és ha ilyenbe kerülne a program, akkor inkább kilép egy hibaüzenettel, ahelyett hogy csak állna ott az idők végezetéig. Persze ennél bonyolultabb dolgokat is lehet csinálni, ízelítőül néhány alapvető függvény (a típusokból jól látszik, hogy mivel változókról van szó, az egész biznisz az IO monádban zajlik):

newMVar      :: a -> IO (MVar a)
newEmptyMVar :: IO (MVar a)
putMVar      :: MVar a -> a -> IO ()
takeMVar     :: MVar a -> IO a
tryTakeMVar  :: MVar a -> IO (Maybe a)  — ez nem vár

Egyébként rengeteg monád van még a Maybe-n és az IO-n kívül is, kezdve magukkal a listákkal (házi feladat kitalálni, hogy hogyan) az igen hasznos State monádokig (melyekkel titokban változókat használó, de összességében mégis pure függvényeket írhatunk, mint pl. egy imperatív quicksort verzió, destruktív update-ekkel).

És a konklúzió? A Haskell tulajdonképpen imperatív nyelvnek sem utolsó… :)

Categories: Programozás | Tags

44 Responses so far.

  1. avatar Murphy says:

    Mi van srácok? Itt a Haskell cikk, és még senki nem szólt hozzá? :)

  2. avatar aha says:

    Mi az a Haskell ?:)

  3. avatar blala says:

    alsó sor legelső link? :)

  4. avatar kt says:

    Ez a Haskell nagyon állat. :D
    Ki kellene próbálni egyszer. :)

  5. avatar pezia says:

    en most vesztettem el a fonalat (lehet mert az elozoekben leirtakat elfelejtettem:) )

  6. avatar blala says:

    Hallo, adminok, editalta valaki rajtam kivul a cikket? Csak mert eltunt par karakter :) Szoval az e107 “okossaga” miatt a Haskell cikkeket nem lehet utolag editalni; a “szerkesztes” ugy megy hogy minden alkalommal ujra copy-pastelem az egesz cikket html forrmaban…

    (na, visszaallitottam a korabbi allapotot)
    [ módosítva Nov.15. 21:16 ]

  7. avatar slyspy says:

    én mindent tagadok.

  8. avatar blala says:

    pezia: hat olvasd ujra oket :)

    beast: hajra! http://haskell.org, en a GHC-t ajanlom letoltesre, tanulasra meg “yet another haskell tutorial” cimut, elso korben.

  9. avatar Murphy says:

    blala: mikor lathatova teszem, olyankor ugye betolti a cikket, es kimenti, siman lehet, hogy igy elbassza… :/

  10. avatar blala says:

    ja, en is erre gyanakodtam kozben.

  11. avatar Bery says:

    Na, én ennél a cikknél értettem meg, hogy mire jó a Haskell: ha meg akarsz felelni annak a tévhitnek, hogy a programozás egy nagyon misztikus dolog, csupa zagyva jellel, és minimum a mandarin nyelvjárás szintjén levő érthetetlenséggel, akkor használj Haskell-t ;-)

  12. avatar abcug says:

    azert kell has, mert kulonben az oldaladon kifolyna a sor amit lenyelsz :)

  13. avatar kt says:

    blala: köszi a linket! Bele is vetem magam. :D

  14. avatar blala says:

    abcug :DDD

    Bery: Dehogy, a Haskell szintaxis maximum szokatlan, es az egyetlen dolog ami miatt elsore komplikaltnak tunhet, az az hogy szintaxis felol kozelitve a Python antitezise: Pythonban ugye az a filozofia, hogy mindenre egyetlen “felszentelt” megoldas van (“There should be one—and preferably only one—obvious way to do it”); Haskellben meg az hogy mindenre sok megoldas van, es a programozora bizzak hogy melyik tetszik neki (es persze szabadon lehet oket keverni is).

    beast: Sok sikert! (es ne add fel az elso akadalyoknal, csak tul kell rajtuk lendulni, es utolag minden magatol ertetodonek es termeszetesnek fog tunni :) en is folyamatosan tanulok uj dolgokat meg)

  15. avatar Bery says:

    Blala: teljesen igazad van, csak poénkodtam, mert fáradt vagyok ahhoz (meg lusta :)), hogy komolyan értelmezzem a dolgot. De nyilván csak az idegenség érzése ez, meg a szokatlanságé. Egyébként valóban frappánsan lehet megfogalmazni algoritmusokat Haskell(nincskötőjel)ben, ez tény.

    [ módosítva Nov.17. 10:26 ]

  16. avatar blala says:

    Slyspy szerint a ‘Haskellben’-t kotojel nelkul kell irni. (A lektor velemenyet hallottak, transzcendentalis mediumon at kozvetitve. Uk-uk-uk-ded-uk-ded-anyad udvozletet kuldi!).

  17. avatar blala says:

    ha nem irtok valami konstruktiv kommentet most azonnal bazdmeg, akkor nem lesz tobb ilyen temaju cikk (azt meg nem sikerult eldontenem hogy ki jar rosszabbul ezzel a felallassal :)

  18. avatar zoom says:

    Minden csoda 3 részig tart :))

  19. avatar pontscho says:

    Folytasd most azonnal bazdmeg, kulonben a tobbit sem fogom elolvasni! :)
    [ módosítva Nov.22. 07:47 ]

  20. avatar christoph says:

    én mindig érdeklődve olvasom a haskell cikkeket, csak c-ben se vagyok nagyon jó, és a haskell most még nehezebbnek tűnik. szóval szerintem folytasd!

  21. avatar slyspy says:

    én meg nem értem de én is olvasom.

  22. avatar Jedi says:

    Most nem azért a 10 fillérért, de blalán kívül írt már vki “‘Hello World”-nél komplexebb progit Haskellben? :) Egyébként meg klafa a cikk. :)

  23. avatar Bery says:

    Végre van valami kóder cikk is, szóval abba ne hagyd! :)

  24. avatar blala says:

    Jedi: Hogyne (bar ha a scene.hu kozonsegere szoritkozunk, akkor azert nem 100% :))

    Par pelda: Haskell az iparban;
    X Windows ablakkezelo,
    revision control system

  25. avatar Edhellon says:

    A darcs-t Haskellben irtak? Mik derulnek ki… :)

  26. avatar Geri says:

    -Ki találta ki ezt a nyelvet?
    -A többiek miért nem verték agyon?

  27. avatar pohar says:

    Geri:
    “Mi az Haskell, és miért jó? (első rész)

    Egy Haskell Brooks Curry nevű amerikai matematikusról nevezték el”

  28. avatar pontscho says:

    -Ki talalta ki ezt a Gerit?
    -A tobbiek miert nem vertek agyon?

    A biologiai/technologiai diverzitas eleg jo indok erre. Raadasul Haskellnek boven van letjogosultsaga, foleg a tudomanyos eletben. Ahogy a LISP-nek az AI-nal, az Ada-nak a katonai rendszereknel (katonai szerver, rotfl). Mindennek megvan a maga celja. Maximum nem ismerted fel.

    [ módosítva Feb.23. 14:34 ]

  29. avatar Travis says:
    A többiek miért nem verték agyon?

    Obi-Wan Kenobi: Only a Sith deals in absolutes.

  30. avatar blala says:
    wrote
    -Ki találta ki ezt a nyelvet?
    -A többiek miért nem verték agyon?

    Mert egyutt talaltak ki :)

    http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/index.htm

    (ps. pohar, nem o talalta ki, csak rola neveztek el. Tudod, mint a Pascal :)
    [ módosítva Feb.23. 18:31 ]

  31. avatar Edhellon says:

    …vagy az Ada. :)

  32. avatar teo says:

    blala – te olvastad is mit irt pohar? :D

  33. avatar pohar says:

    blala: pohar, nem o talalta ki, csak rola neveztek el.

    pohar: “Egy Haskell Brooks Curry nevű amerikai matematikusról nevezték el”

  34. avatar Geri says:

    Megvan! Azért nem verték agyon, mert amikor elolvasták a specifikációkat, visszafelé kezdett verni a szívük.

  35. avatar slyspy says:

    Egymástól idézgettek most?

  36. avatar pohar says:

    slyspy | febr.23. 22:34
    Egymástól idézgettek most?

    pohar | febr.23. 20:04
    blala: pohar, nem

  37. avatar Bery says:

    Geri: -Ki találta ki ezt a nyelvet?

    Travis: Obi-Wan Kenobi

    Edhellon: …vagy az Ada.

    Blala: nem o talalta ki

    teo: te olvastad is?

    Geri: Megvan!

    blala: Mert egyutt talaltak ki :)

    Geri: A többiek miért nem verték agyon?

    pontscho: A biologiai/technologiai diverzitas eleg jo indok erre.

    Edhellon: A darcs-t Haskellben irtak?

    pontscho: nem ismerted fel.

    ;)

  38. avatar Gargaj says:

    *függöny*

  39. avatar Geri says:

    Szegény Kórus még szerepet sem kapott

    =(

  40. avatar Travis says:

    Ha majd egyszer készítek egy programozási nyelvet, akkor Blaláról fogom elnevezni.

  41. avatar pohar says:

    én Geriről

  42. avatar slyspy says:

    Én obivankenobiról. A tieteket is.

Leave a Reply

You must be logged in to post a comment.

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