☰ Menu

Scene.hu

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

Haskell_Logo_w.pngA mai epizód tartalmából: listák, ADT, pattern matching, rekurzió (no és persze protagonistánk, a zipWith sem veszett el!). Az első rész itt olvasható, ha valaki lemaradt volna.

vagas.pngKezdjük talán ott, ahol a múltkor abbahagytuk:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = (f x y) : (zipWith f xs ys)
zipWith _ [] _ = []
zipWith _ _ [] = []

Mit is jelent ez pontosan? Az első sort ugye már elvileg értjük; egyébként ez az a sor a négyből, amelyik felesleges, ezt ugyanis a compiler kitalálja a másik háromból. A maradék három sor a függvény definíciója; ezekben a pattern matching névre hallgató, elég kényelmes fícsört figyelhetjük meg. Azonban ahhoz, hogy minden kristálytiszta legyen, előbb szólnom kellene pár szót a listák felépítéséről…

A lista definíciója a funkcionális nyelvekben általában úgy néz ki, hogy a lista az vagy egy üres lista, vagy pedig egy elem (a legelső, szaknyelven head), plusz a maradék (tail), ami megint egy lista. Haskell szintaxissal ezt írhatjuk például így:

data List a = Empty
            | Cons a (List a)

(Azért Cons, mert… őőő, tradícionális okokból :). Ez egy típusdefiníció, pontosabban egy típuskonstruktor definíciója: a List egy tetszőleges a típusból csinál egy újabb típust (a List a-t). Az egyenlet jobboldalán pedig a típus lehetséges értekei állnak: vagy az Empty nevű szimbólum, vagy pedig egy (a Cons szóval jelölt) pár, aminek az első tagja a típusú, a második pedig List a típusú. Vegyük észre, hogy gyakorlatilag szó szerint ugyanaz a definíció, mint amit magyar szavakkal írtam előtte (meg azt is, hogy ez egy rekurzív definíció: A lista definíciójában szerepel a lista fogalma… :)

Hogy világosabb legyen, az [1,2,3,4] lista az ideiglenesen bevezetett új jelölésrendszerrel így nézne ki:

Cons 1 (Cons 2 (Cons 3 (Cons 4 Empty)))

A Haskell definíció szó szerint ugyanez, csak List a helyett [a]-t írnak, Empty helyett []-t, és Cons helyett (:)-ot, amit infix módon is lehet írni, így az előző példa 1:2:3:4:[]-vé egyszerűsödik (zárójelek sem kellenek, mivel a : jobbasszociatívnak van deklarálva). Az [1,2,3,4] “klasszikus” jelölés pedig titokban csak egy rövidítés az előzőre.

A listának ezen definíciója (vajon még hányszor kell leírjam ma ezt a szót? :) egyébként egy remek példa az Algebraic Data Types fogalmára, amiről később még lesz szó (bináris fák, reszkessetek!)

Ezen a ponton tehát már remélhetőleg értjük, mik is azok a kettőspontok a fenti kódrészlet második sorában. Elemezzük akkor, mi is van odaírva:

zipWith f (x:xs) (y:ys) = (f x y) : (zipWith f xs ys)

Kiolvasva ez valami ilyesmit takar: ha a zipWith első paramétere az f függvény, a második paramétere egy nemüres (!) lista, melynek első eleme x, a maradék pedig xs, végül hasonlóan, a harmadik egy nemüres lista, melynek első eleme y, a többi pedig ys, akkor a végeredmény egy nemüres lista, melynek első eleme f x y (azaz az f függvény kiértékelve az x és y paraméterekkel), a maradék pedig… Hoppá, ugyanez a zipWith a listák maradékaival! (lábjegyzet: Ez egy rekurzív függvénydefiníció, ami nagyon gyakori a funkcionális nyelvekben. Szerencsére nem kell aggódni, hogy betelik a verem, mert éppen gyakoriságuk miatt a funkcionális nyelvekben a tail recursion optimalizációja kötelező gyakorlat…)

Elég logikus, nem?

A maradék két sor pedig azt mondja meg, hogy mi történjen, ha valamelyik lista éppen üres; ehhez még annyit árulnék el, hogy az aláhúzás karakter a Haskell pattern matching szintaxisában a “joker”: mindegy hogy mi áll a helyén.

Nos, úgy érzem, a főhős ezen a ponton gyakorlatilag meghalt, de nem kell aggódni, tekintve hogy ez egy sorozat, lesznek újabb hősők :). És tényleg, ezen a ponton reszketve bár, de belép a színre… a Bináris Fa!

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

(Házi feladat egy olyan verzió kidolgozása, ahol az elágazásokban pedig b típusú objektumok ülnek.)

Na és mit lehet kezdeni egy bináris fával? Hát például bejárni a leveleit balról jobbra!

walk :: Tree a -> [a]
walk (Branch left right) = walk left ++ walk right
walk (Leaf x) = [x]

folyt. köv.

(a TV-ből ugye jól tudjuk, hogy mindig a legizgalmasabb pillanatokban kell reklámmal megszakítani a sorozatokat… :)

Categories: Programozás | Tags

30 Responses so far.

  1. avatar Jimmi says:

    Ezzel tényleg nagyon gyors particle engine-t lehetne írni. (Megláttam a lényeget, ugye?)

  2. avatar pontscho says:

    Tetszik. Kelloen el van borulva. :)

  3. avatar pasy says:

    demó or dáj

  4. avatar FooLman says:

    Ezzel tényleg nagyon kockának lehet lenni azonnal :)
    Na EZ a lényeg…

  5. avatar pohar says:

    de ezzel is ugyanúgy kell hívogatni az OpenGL függvényeket, aztán csá :)

  6. avatar Gargaj says:

    csak ezzel kozelebbinek tunik a deadline :)

  7. avatar pezia says:

    tok jo, hogy vegre a prolog oktatast tudom hasznositani valaminek a megertesehez :)

  8. avatar Bery says:

    Haskell, minden háztartásba ez kell! ;-))))

  9. avatar Oswald says:

    bevallom férfiasan hogy nem értek egy kukkot se :)

  10. avatar blala says:

    ennyire benan probalok magyarazni? ne csinaljatok ezt velem… :)

  11. avatar slyspy says:

    látom erre senki nem mer válaszolni. :)

  12. avatar Murphy says:

    Én nem tudom, hogy a blala magyaráz-e rosszul, mert nem értem. :D

  13. avatar Gargaj says:

    sztem 50-50 :D

  14. avatar Bery says:

    Hát sejtem én, hogy miért mondod te, Blala, hogy jó ez, csak momentán most nem ez érdekel a programozásban, hanem az eredmény, meg a hatékonyság, de ez utóbbit még nem látom :)

  15. avatar Jimmi says:

    Én értem a cikket, de ha nem tanultam volna fél évig Prologot meg SML-t egyetemen, akkor lehet, hogy nem érteném…
    Fun codingra jónak tűnik ez a Haskell, de ennek mintájára lehetne mondjuk egy Python/Ruby cikk is, mert az is fun, csak az még használható is ráadásul :) (Lásd még: Die Ewigkeit schmerzt by neuro)

  16. avatar slyspy says:

    Blala vazze add már ki a demót, hadd lássa mán mindenki, hogy ezt is lehet használni!

  17. avatar slyspy says:

    Hát jó, akkor ilyen már van, Python kifújt.

  18. avatar Gargaj says:

    es raadasul nem is ez volt az elso pythonos demo. ;)

  19. avatar blala says:

    Na akkor kicsit valaszolgatok.

    pontscho: Ez meg nincs is elborulva, eddig barmelyik funkcionalis nyelv lehetne; meg epp hogy csak a felszint se karcolgatjuk :)

    pohar: reszben igen, mert a vegeredmeny szempontjabol viszonylag mindegy miben programozik az ember, de a bugok, a hatekonysag, meg a fun szempontjabol nezve viszont kurvara nem mindegy

    Bery: pedig pont a hatekonysagrol van szo :) 500-1000 sorban mar eleg komoly dolgokat lehet csinalni. Letezo peldak: X window manager, webszerver… Na meg a debuggolasra forditott ido is igen alacsony.

    Jimmi: ja, az SML az elegge hasonlo dolog asszem (a prolog nem). Ez kicsit ujabb, meg mereszebben exploraljak a PL design space-t :) Viszont tevedes, hogy csak fun codingra jo. A python kis hekkelesekre eleg jo, de komolyabb projectet en dinamikus nyelvben nem allnek neki csinalni, ha nem muszaj… (espedig a vegtelenszer tobb buglehetoseg miatt, meg a karbantarthatosag miatt)
    [ módosítva Oct.19. 15:24 ]

  20. avatar Jimmi says:
    A python kis hekkelesekre eleg jo, de komolyabb projectet en dinamikus nyelvben nem allnek neki csinalni, ha nem muszaj… (espedig a vegtelenszer tobb buglehetoseg miatt, meg a karbantarthatosag miatt)

    Igen, pont ezért nem látom a Haskellt sem alternatívának nagyobb projektekhez. De egy demo persze még elég picinyke projektnek számít.

  21. avatar blala says:

    Pontosan ezert jo alternativa a Haskell nagyobb projectekhez. A demo persze tenyleg kicsi project, de amikor deadline elott 12 oraval kurvara atalakitod a program belso strukturajat, es elsore mukodik, az eleg meggyozo… Szerintem.

    na itt egy link. Credit Suisse, anyone? Egyebkent pl az Intel is ha jol emlekszem valami ML-jellegu nyelven nyomja a hardware verification projecteket. Peldaul.

  22. avatar Gargaj says:
    wrote
    A python kis hekkelesekre eleg jo, de komolyabb projectet en dinamikus nyelvben nem allnek neki csinalni, ha nem muszaj… (espedig a vegtelenszer tobb buglehetoseg miatt, meg a karbantarthatosag miatt)

    EVE Online szerver pl.?

  23. avatar Jimmi says:

    blala: Az, hogy valami elsőre működik, inkább kóderfüggő, imho. Azt ugye érzed, hogy a “deadline elott 12 oraval kurvara atalakitod a program belso strukturajat, es elsore mukodik” azért eléggé semmitmondó kijelentés :)
    Gargaj: Respect a srácoknak, hogy az EVE szervert Pyhtonban össze tudták hozni, de ettől még nem ez a megfelelő eszköz rá. :) (Persze ha lehet választani, akkor inkább Python, mint Haskell…)
    [ módosítva Oct.20. 16:26 ]

  24. avatar blala says:

    Jiimmi: a nagyon keves C kodreszletet a dologban viszont napokig debuggoltam. Ugyanaz a koder, azt ugye erzed? :)
    A masik bekezdessel meg az van, hogy az elso felevel egyetertek, a masodikkal pedig nem. Milyen meglepo :)

  25. avatar Charlie says:
    wrote
    Egyebkent pl az Intel is ha jol emlekszem valami ML-jellegu nyelven nyomja a hardware verification projecteket.

    … most ha genyo lennek akkor aszondanam, hogy ez sokmindent megmagyaraz… ;) Aztan mindenki ertse ahogy akarja. :P

  26. avatar Charlie says:

    Ja es egyebkent, jo tudni, hogy mitol sikeres egy programozasi nyelv. Nem tudok vitatkozni. De most igy komolyan. :)

  27. avatar Murphy says:

    A C# novekvo tendenciat mutat, pont a java elleneben, igy megdolni latszik az elv :)

  28. avatar blala says:

    Ja, es C# az azt hiszem hogy nem is olyan rossz nyelv, bar igazabol nem ismerem. Meg van ilyen hogy F#, amit szinten a Microsoft csinal, csak a research dept, es lenyegeben egy .net-es ML dialektus; es most felkarolta a “product dept” is. Meg a parhuzamos programozas nehezsege miatt teret fognak nyerni a funkcionalis nyelvek ugyis.

  29. avatar Gargaj says:

    murphy: nyilvan mert a szakallat is meg lehet noveszteni :)

Leave a Reply

You must be logged in to post a comment.

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