Haskell
A Wikipédiából, a szabad enciklopédiából.
Tartalomjegyzék |
[szerkesztés] Bevezető
A Haskell tisztán funkcionális, lusta kiértékelésű, polimorf típusokat és magasabb rendű függvényeket tartalmazó programozási nyelv. A nyelv ezzel meglehetősen különbözik a ma általában használatos nyelvektől. A nyelvet Haskell Brooks Curry amerikai matematikusról kapta nevét, aki a matematikai logikában kifejtett munkássága révén hozzájárult a funkcionális nyelvek elméleti alapjainak fejlődéséhez. A Haskell nyelv alapja a lambda-kalkulus.
A nyelv tömörségét és kifejezőképességét bemutató rövid példaprogram, a gyorsrendezés megvalósítása:
gyorsRendezes [] = []
gyorsRendezes (x:xs) = gyorsRendezes kisebbElemek ++ [x] ++ gyorsRendezes nemKisebbElemek
where
kisebbElemek = [y | y <- xs, y < x]
nemKisebbElemek = [y | y <- xs, y >= x]
Az (rekurzív) algoritmus a következő: Ha üres a lista, akkor rendezett. Egyébként vesszük az első elemet és sorban összefűzzük a kisebb elemek rendezett listáját, az elemet tartalmazó listát, valamint a nem kisebb elemek rendezett listáját. (Itt [] az üres lista, x a paraméterként átadott lista első eleme, xs a maradék lista, ++ a lista-összefűzés operátora. Az utolsó előtti sorban a halmazjelölés-szerű listaelőállító konstrukció szerepel, jelentése: olyan y-ok listája, ahol y az xs eleme, és y kisebb mint x.)
[szerkesztés] A nyelv nagyon rövid története
A Haskell aránylag fiatal nyelv, de a gyökerei elég mélyre nyúlnak az időben. 1978-ban megjelent John Backus cikke, amelyben leírja az FP nyelvet, amely magasabb rendű függvényeket használó tiszta funkcionális nyelv volt és amely később nagy hatással volt a funkcionális nyelvek fejlődésére. Körülbelül ebben az időben az Edinburgh-i Egyetemen kifejlesztik az ML nyelvet, amelyet akkor még csak egy tételbizonyító programhoz akartak használni, de később rájöttek, hogy általános célú nyelvként is megállja a helyét. 1985-86-ban fejlesztették ki Miranda nyelvet, amelyet az 1987-ben megalakult Haskell nyelvi bizottság a Haskell alapjául akart felhasználni. A Miranda tervezőjét és jogtulajdonosát ez a lehetőség azonban nem érdekelte.
A Haskell nyelv első leírása 1990-ben jelent meg. Ez volt a Haskell 1.0. Ezután a nyelv fejlődésnek indult, és 1997-ben már az 1.4-es változatnál tartottak. 1997-ben az amszterdami Haskell Workshop alkalmával a nyelv tervezői belátták, hogy egy stabil nyelvi szabványra van szükség. 1998-ban született meg a ma is érvényben lévő Haskell 98 szabvány. Ennek javított változata 2003-ban jelent meg – ez azonban már csak kisebb korrekciókat, hibajavításokat tartalmaz.
[szerkesztés] A Haskell nyelv dióhéjban
[szerkesztés] Típusok
A Haskell erősen (szigorúan), vagy statikusan típusos nyelv, így ahol a nyelv a T típust várja, csak T típusra kiértékelődő kifejezést fogad el
Több érték tárolása a listákkal és a tuple típussal lehetséges. A listák homogének, tehát csak egyféle adattípust tartalmazhatnak. A listák elemszáma nem része a típusnak, ellentétben a tuple típussal, mellyel rendezett párok, hármasok stb. létrehozására használható.
[szerkesztés] Végtelen listák
A listáknak nem kell feltétlenül végesnek lenniük; a lusta kiértékelésnek köszönhetően a véget nem érő listáknak csak a szükséges elemei értékelődnek ki. Például:
egyesek = 1:egyesek
Az első n elem biztonságosan felhasználható, csak az elemek megszámlálása vezet végtelen ciklushoz. A lusta kiértékelésnek köszönhető az is, hogy a végtelen lista nem létező utolsó eleme után is írhatunk elemeket:
egyesek ++ [2,3,4,5,6,7,8,9]
[szerkesztés] Függvények
A függvények nulla vagy egy paraméter alapján pontosan egy értékkel térnek vissza. A Haskell fontos tulajdonsága, hogy ugyanaz a függvény ugyanazokkal a paraméterekkel mindig ugyanúgy tér vissza. Ez átláthatóbbá teszi a nyelvet, ellenben megkívánja, hogy a kimenetet és bemenetet ne függvények végezzék.
A lusta kiértékelés része, hogy függvényhíváskor a paraméter nem értékelődik ki, csak ha szükséges.
A függvények rendelkeznek az adattípusok tulajdonságaival. Megadhatók paraméterként és visszatérési értékek is lehetnek függvények.
Új függvények létrehozása történhet a lambda-jelöléssel, például
\x -> 10-x
Létező operátorok is alkalmazhatók függvényként
(10-)
Az így létrehozott függvényeket leggyakrabban paraméterként adják meg más függvényeknek. Nevesített függvények is létrehozhatók:
TizMinusz x = 10 - x
Új adattípusok létrehozása adatkonstruktorokkal lehetséges. Például a logikai típusnak két, paraméter nélküli konstruktora van, az egyik az igaz, a másik a hamis értékre.
Magasabbrendű típusokból típuskonstruktorral lehet alkalmazható típusokat létrehozni.
[szerkesztés] Algebrai típusok
A Haskell-ben a strukturált típusok mellett algebrai típusokat is létrehozhatunk. Példa:
data Szin = Feher | Fekete | Kek | Sarga | Piros | Zold data Minta = Kockas | Csikos | Halas | Macis
Itt a Szin azonosító egy új algebrai típust, a Feher, Fekete és a többi jobb oldalon szereplő azonosító pedig konstruktort jelöl. A konstruktorok neve nagy betűvel kezdődik. A definíció után már leírhatunk pár értéket a típusával együtt:
Fehér :: Szin [Kek, Zold] :: [Szin]
A konstruktoroknak paramétereket is adhatunk:
data Minta = Kockas | Csikos | Halas | Macis
data Labda = SzinesLabda Szin
| MintasLabda Szin Minta
Ez esetben például a következő Labda típusú értékeket írhatjuk föl:
SzinesLabda Piros :: Labda MintasLabda Feher Csikos :: Labda
[szerkesztés] Paraméteres típusok
Ez a példa egyben egy paraméteres és rekurzív típus, amellyel bináris fát ábrázolhatunk:
data Fa a = Level a
| Elagazas (Fa a) (Fa a)
Az a típusváltozó egy konkrét értéknél behelyettesítődik valamilyen (paraméter nélküli) típussal:
Level 1 :: Fa Integer Elagazas (Level 'x') (Elagazas (Level 'y') (Level 'z')) :: Fa Char
A Fa a típuskifejezést polimorf típusnak, a Fa Integer típuskifejezést pedig a Fa a polimorf típus példányának nevezzük.
[szerkesztés] Függvények alkalmazása
[szerkesztés] Curry-jelölés
A Haskellben elvileg csak egyparaméteres függvények vannak. Mégis valahogy létre tudunk hozni több paraméteres függvényeket kerülő úton. Először nézzünk egy példát:
add1 :: Integer -> Integer -> Integer add1 x y = x + y + 1
Az add1 függvény típusa Integer -> Integer -> Integer, ami zárójelezve így néz ki: Integer -> (Integer -> Integer) (a -> operátor jobbra köt). Ez azt jelenti, hogy az add1 függvény egy Integer paramétert vár, és egy Integer -> Integer típusú függvényt ad vissza. Az ilyen függvényeket nevezzük Curry-jelölésűnek.
Egy, a programozástól talán távolabbi példával is szemléltethető az alapgondolat. A logaritmus fogalmára úgy is gondolhatunk,
- mint kétparaméteres függvényre: első paraméterként az alapot veszi át, és még egy számot („a keresett hatványt”), és visszadja a megfelelő értéket. Pl. a 2 és a 8 esetén 3-at.
- De gondolhatunk a logaritmus fogalmára úgy is -- és a logab jelölés is ezt sugallja -- hogy a logaritmus egyparaméteres függvény: azonban számból nem számot, hanem függvényt állít elő. Tehát a log28 jelölés tulajdonképpen két függvényalkalmazást is magában foglal: először a log függvényt a 2 alapra alkalmazva megkapjuk a log2 függvényt, majd az (épp imént kapott) log2 függvényt a 8-ra alkalmazva megkapjuk a 3-at.
A többparaméteres függvények fogalma tehát megragadható egyparaméteres függvények alkalmazás révén is (ha megengedjük, hogy a függvények értékül függvényt adhassanak vissza).
[szerkesztés] Függvényalkalmazás
A függvényalkalmazás jele az egymás mellé írás, tehát
inc 1 => 2
(A => jel a kifejezés értékét jelöli.)
Az alkifejezéseket zárójelek közé zárjuk:
inc (inc 1) => 3
A függvényalkalmazás balra köt, tehát a fenti add1 Curry-jelölésű függvényt így használjuk:
add1 2 3 => 6
amely kifejezés tulajdonképpen ezt jelenti:
(add1 2) 3 => 6
Ebből következik, hogy az (add1 2) egyparaméteres függvény tulajdonképpen 3-at ad az Integer típusú paraméteréhez.
[szerkesztés] Esetek, minták és őrök
A strukturált adatok elemeinek szétválasztására, illetve az algebrai típusok eseteinek megkülönböztetésére a case-kifejezést használjuk.
Definiáljunk egy függvényt, amelyik összeadja a paraméterként átadott egész pár tagjait!
addpair :: (Integer, Integer) -> Integer
addpair p = case p of
(x, y) -> x + y
addpair (2, 3) => 5
Írjunk egy függvényt, amelyik a Szin típusú paramétert vár, és Fekete-re 1-et, Feher-re 2-t, egyéb szín esetén 0-t ad vissza!
szinSzam :: Szin -> Integer
szinSzam szin = case szin of
Fekete -> 1
Feher -> 2
_ -> 0
A példa magáért beszél. Az _ akármelyik értéket jelöli. A case kifejezésben a lehetőségeket sorban kell vizsgálni, tehát az _-ra csak akkor kerül sor, ha előtte nem találtunk megfelelő értéket.
Az előző két függvényt mintákkal is megírhatjuk:
addpair :: (Integer, Integer) -> Integer addpair (x, y) = x + y
szinSzam :: Szin -> Integer szinSzam Fekete = 1 szinSzam Feher = 2 szinSzam _ = 0
A függvény formális paramétere egy minta is lehet. A fenti két definíció jelentése pontosan megegyezik a case kifejezést használó definícióval. A paraméter helyén csak lineáris minta lehet, azaz minden változó csak egyszer szerepelhet benne (ebben különbözik a Prologtól, amelyben egy változó többször is szerepelhet a mintában).
Az esetek mellett őröket is használhatunk a függvények megadásánál:
butaPelda :: Integer -> Integer -> Integer
butaPelda x y | x > 0 = x + y
| otherwise = x * y
Ez a függvény összeadja a két paraméterét, ha x pozitív, egyébként összeszorozza.
Az őr-kifejezések mindig logikai értékűek. A Haskellben a logikai érték egy előre definiált algebrai típus:
data Bool = True | False
[szerkesztés] Az if-kifejezés
A más programozási nyelvekben általában szokásos if-kifejezés a Haskellben is megtalálható, pélául a butaPelda függvényünket így is megadhattuk volna:
butaPelda x y = if x > 0 then x + y else x * y
A Haskell-ben azonban az if-kifejezést a case-kifejezésre vezetjük vissza, az
if feltétel then igaz-ág else hamis-ág
kifejezés megfelel a
case feltétel of True -> igaz-ág False -> hamis-ág
kifejezésnek.
