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.