Haskell (programozási nyelv)

Haskell
Paradigma	funkcinális, lazy/gyengén típusos, moduláris
Jellemző kiterjesztés	.hs, .lhs
Megjelent	1990
Tervező	Simon Peyton Jones, Lennart Augustsson, Dave Barton, Brian Boutel, Warren Burton, Joseph Fasel, Kevin Hammond, Ralf Hinze, Paul Hudak, John Hughes, Thomas Johnsson, Mark Jones, John Launchbury, Erik Meijer, John Peterson, Alastair Reid, Colin Runciman, Philip Wadler
Fejlesztő	Paul Hudak Lennart Augustsson John Hughes Simon Peyton Jones Erik Meijer Philip Wadler
Utolsó kiadás	Haskell 2010 (2010. július)
Típusosság	statikusan típusos, erősen típusos, inferred
Dialektusok	Helium, Gofer, Hugs, Ωmega
Megvalósítások	GHC, Hugs, NHC, JHC, Yhc, UHC
Hatással volt rá	Agda, Bluespec, Clojure, C#, CAL, Cayenne, Clean, CoffeeScript, Curry, Epigram, Escher, F#, Factor, Isabelle, Java Generics, Kaya, LINQ, Mercury, Omega, Perl 6, Python, Qi, Scala, Timber, Visual Basic 9.0
Befolyásolt nyelvek	Alfl, APL, Clean, FP, Gofer, Hope and Hope+, Id, ISWIM, KRC, Lisp, Miranda, ML and Standard ML, Lazy ML, Orwell, Ponder, SASL, SISAL, Scheme
Operációs rendszer	multi-platform
Weboldal

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 nyelv Haskell Brooks Curry amerikai matematikusról kapta a 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.)

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 a 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. 2010-ben jelent meg a következő nyelvi szabbvany, melyben appróbb modositasokon felul megtalálható a FFI azaz Foreign Function Interface mely más nyelven írt függvénnyek Haskellbe emeléset teszi lehetővé.

A Haskell nyelv dióhéjban

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ó.

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]

Függvények

A Haskell függvényei, megfelelnek annak a matematikai koncepciónak is, hogy minden függvény egy paraméteres. (pl. Egy egyébkent két paraméteres függvény lerható egy olyan függvénnyel, mely egy paramétert vár, és egy egy paraméteres függvényt ad vissza.) A Haskell fontos tulajdonsága, hogy ugyanaz a függvény ugyanazokkal a paraméterekkel mindig ugyan azzal az értékkel tér vissza. Ez a tulajdonság, függvények tisztaságából, mellékhatás-mentességéből fakad. Ez átláthatóbbá teszi a nyelvet, ellenben megkívánja, hogy a kimenetet és bemenetet ne egyszerű függvények végezzék, hiszen ezek jellemzően mellékhatásos műveletek.

A lusta kiértékelés része, hogy függvényhíváskor a paraméter nem azonnal értékelődik ki, csak a legelső olyan ponton, ahol valóban szükség van az értékére.

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 is, például

\x → 10-x

Létező operátorok is alkalmazhatók függvényként, ezeket szeleteknek nevezzuk

(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

Haskellben három típuskonstrukciós lehetőség van. Legegyszerűbb a type kulcsszóval hasznalható, csupan típusszinonímát hoz letre

type Name = String

newtype mar új típus. Technikailag konstrukorokat használ mint az algebrai adattípus, azonban ez forditás folyamán mar eltűnik.

newtype Name = Name Sting

Harmadik lehetőseg a data kulcsszó. Ezzel algebrai adattípusokat adhatunk meg

data Name
    = Name Sting
    | NoName

A Haskell alapértelmezett könyvtárában (a Prelude-ben) található Bool típus definíciója is így néz ki

data Bool
    = False
    | True

Algebrai adattí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 adattí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

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.

Függvények alkalmazása

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. Például a 2 és a 8 esetén 3-at.
• De gondolhatunk a logaritmus fogalmára úgy is -- és a $\mathrm {log} _{a}b$ 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 $\mathrm {log} _{2}8$ jelölés tulajdonképpen két függvényalkalmazást is magában foglal: először a $\mathrm {log}$ függvényt a 2 alapra alkalmazva megkapjuk a $\mathrm {log} _{2}$ függvényt, majd az (épp imént kapott) $\mathrm {log} _{2}$ 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).

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.

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

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.

Osztályok

Haskellben, (és általában a Funkcionális nyelvekben) az osztályfogalom eltérő az imperatív nyelvekben megszokottaktól. Imperatív nyelvekben az osztályok az objektumokat osztályozzák, Haskellben a típusokat. Leginkább az interfész fogalomhoz áll kozel, de annal többet képes kifejezni.

Prelude Show osztálya

class Show a where
  showsPrec :: Int -> a -> ShowS
  show :: a -> String
  showList :: [a] -> ShowS

Adatok szoveggé alakítására. Ennek példánya pl. Int, Integer, Bool, de maga a String is.

Feltűnhet, hogy a típusváltozó, tetszőleges helyen állhat a metódusainak szignatúrájában. Ennek oka, hogy a Haskell tervezői nem látták szukségét egy uj szintaktikus elem beemelésének. Egy fuggveny hivasanal nem szamit hogy az egy egyszeru fuggveny, vagy egy metodus. Ennek meg egy pozitiv hozadeka, hogy egy metodus, illetve osztály több típushoz is tartozhat (lásd: Több paraméteres osztályok).

Egy osztály definiálásakkor, lehetőség van egyes függvények alapértelmezett implementációjának megadására is. Show osztály példányosításakkor is csak show függvényt kell megadni. Egy példa példányosításra:

data Name = NoName
          | Name String
instance Show Name where
    show NoName = "no name"
    show (Name n) = n