Haskell programozási nyelv
A Wikipédiából, a szabad lexikonbó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, értékek
A Haskell erősen (szigorúan), vagy statikusan típusos nyelv. A Haskell-rendszer egy program végrehajtása előtt (pl. fordításkor) leellenőrzi a típusok helyes használatát, tehát például az 'a' + 4 kifejezést már nem fogadja el - ebben különbözik a gyengén, vagy dinamikusan típusos nyelvektől, ahol egy hasonló kifejezésnél a kiértékelése során kapunk hibajelzést.
[szerkesztés] Egyszerű, strukturált és függvénytípusok
Minden Haskell-kifejezésnek meghatározott típusa van. A nyelvben a típusok leírására típuskifejezést használunk. A kifejezések, értékek mellett feltüntethetjük azok típusát is a :: szintaktikai elem után: ez a típusjelölés.
Egész:
3 :: Integer
Karakter:
'c' :: Char
Rendezett pár:
('e', 8) :: (Char, Integer)
Rendezett hármas:
("ablak", 'A', 2)
Lista:
[1, 2, 3] :: [Integer]
A Haskellben kizárólag homogén listák vannak, tehát egy lista minden eleme ugyanolyan típusú.
Füzér:
"ceruza" :: String ['c', 'e', 'r', 'u', 'z', 'a'] :: [Char]
A két fenti kifejezés és típusaik egyenértékűek, tehát a String egyszerűen karakterek listája, tehát [Char].
Függvény:
\ x -> x + 1 :: Integer -> Integer
Ez egy olyan függvény, amelyik egyet ad a paraméteréhez (Ez tulajdonképpen egy lambda-kifejezés, ahol a \ (lejtő, vagy backslash karakter) jelöli a lambdát.) A Integer -> Integer jelölés jelentése: függvény, amelyik egész paramétert vár és egész az értéke.
[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
A Haskell-ben a függvényeket egyenletek sorozatával adjuk meg. Példa:
inc :: Integer -> Integer inc n = n + 1
Az első sorban megadjuk a függvény típusát egy típusjelöléssel, a második sorban pedig a magát a függvényt definiáló egyenletet. (Itt egyetlen egyenlettel adtuk meg a függvényt.)
[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.
Megpróbálom a fogalmat egy, a programozástól talán távolabbi példával szemléltetni. 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.
