Haskell (programozási nyelv)

Haskell

Paradigmafunkcionális, lusta kiértékelés, moduláris
Jellemző kiterjesztés.hs, .lhs
Megjelent1990
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ásHaskell 2010 (2010. július)[1]
Típusosságstatikusan típusos, erősen típusos, inferred
DialektusokHelium, Gofer, Hugs, Ωmega
MegvalósításokGHC, Hugs, NHC, JHC, Yhc, UHC
Hatással volt ráAlfl, APL, Clean,[2] FP,[2] Gofer,[2] Hope és Hope+,[2] Id,[2] ISWIM,[2] KRC,[2] Lisp,[2] Miranda,[2] ML and Standard ML,[2] Lazy ML, Orwell, Ponder, SASL,[2] SISAL,[2] Scheme[2]
Befolyásolt nyelvekAgda, Bluespec, Clojure, C#, CAL, Cayenne, Clean, CoffeeScript, Curry, Epigram, Escher, F#, Factor, Isabelle, Java Generics, Kaya, LINQ, Mercury, Omega, Perl 6, Python, Qi, Rust, Scala, Timber, Visual Basic 9.0
Operációs rendszermulti-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     =  filter (<x)  xs
    nemKisebbElemek  =  filter (>=x) xs

A (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ű lista előállító konstrukció szerepel, jelentése: olyan y-ok listája, ahol y az xs eleme, és y kisebb mint x.)

A nyelv 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,[3] 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 szabvány, melyben apróbb módosításokon felül megtalálható a FFI azaz Foreign Function Interface mely más nyelven írt függvények Haskellbe emelését 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.

A nyelv kényelmi szempontból szintaktikailag megkülönböztet néhány típust, a felhasználó által definiálható típusoktól. Ilyenek a Listák (list), és a rendezett n-esek (tuple).

A listák homogének, tehát csak egyféle adattípust tartalmazhatnak. A listák elemszáma nem része a típusának, ellentétben a rendezett n-esekkel, melyeknek típusából explicit módon kiderül, hány elem tárolására alkalmas.

Típus kikövetkeztetés

Imperatív nyelveknél megszokottaktól eltérően, (funkcionális nyelvekre amúgy jellemző módon) a Haskell nem típusellenőrzést végez fordítás alatt, hanem típus kikövetkeztetést. Ez abból áll, hogy a fordítandó program részkifejezéseit, a rajtuk végzett műveletek alapján megkísérli típussal ellátni. Ha ezzel végzett és az összeállított programban nem talált típusütközést, a program típusilag helyes.

Ez leveszi a programozó válláról a sokszor bonyolult típusok meghatározásának terhét és már fordítási időben típushelyes kódokat garantál, a dinamikus típuskezelés számos előnyével.

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]

Ipari környezetben alkalmaznak un. Strict Haskell fordításokat is, amelyek – mint azt nevük is mutatja – nem lusta kiértékelésűek. Ilyen környezetben természetesen a végtelen listák (és úgy általában a végtelen adatszerkezetek) problémásabbak lehetnek.

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ébként két paraméteres függvény leírható 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 ugyanazzal az értékkel tér vissza. Ez a tulajdonság a 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 nevezzük

(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 használható, csupán típusszinonimát hoz létre

type Name = String

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

newtype Name = Name String

Harmadik lehetőség a data kulcsszó. Ezzel algebrai adattípusokat adhatunk meg

data Name
    = Name String
    | 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 visszaadja 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 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 jelölés tulajdonképpen két függvényalkalmazást is magában foglal: először a függvényt a 2 alapra alkalmazva megkapjuk a függvényt, majd az (épp imént kapott) 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éldá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 közel, de annál többet képes kifejezni.

Prelude Show osztálya

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

Adatok szöveggé 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 szükségét egy új, szintaktikus elem beemelésének. Egy függvény hívásánál nem számít hogy az egy egyszerű függvény, vagy egy metódus. Ennek egy pozitív hozadéka, hogy egy metódus, illetve osztály több típushoz is tartozhat (lásd: Több paraméteres osztályok).

Egy osztály definiálásakor 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ásakor 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

Osztályok alkalmazása

Ha egy típus példánya egy osztálynak, a fordítóprogram ezt az információt természetesen ismeri. Amikor azonban egy típusváltozót használunk pl. egy függvény szignatúrájában, arról a fordító nem garantálhatja, hogy rendelkezik a használatához szükséges feltételekkel. Például, hogy a eleme annak az osztálynak, melynek a metódusát használjuk.

    toString :: (Show a, Show b) => a -> b -> String
    toString a b = show a ++ show b

Erre lehet úgy is gondolni, hogy a is és b is rendelkezik a Show 'tulajdonsággal'

Típusfüggvények

Haskellben lehetőség van ún. típusfüggvények megadására osztályokban. Erre olyan esetekben lehet szükség, ahol egy függvénynek nem csupán a bemeneti paraméterei lehetnek többféle típusúak, hanem a valamely bemeneti paraméterének típusától függően a visszatérési értékének típusa is. Vagy valamely bemeneti paraméterének típusától függően egy másik bemeneti paraméter típusa.

Példaképp: Egy két paraméteres függvény bementi típusai határozzák meg visszatérési értékének típusát is. A bemeneti értékeken végezhető műveleteket ugyan az az osztály szolgáltassa:

class AbsType a where
    type AbsResult
    absAdd :: a -> a -> a
    absMul :: a -> a -> a
    result :: a -> AbsResult a

foo :: (AbsType a) => a -> a -> AbsResult a
foo a b = result (absAdd (absMul a b) a)

Egy lehetséges példányosítás:

instance AbsType Int where
    type AbsResult = String
    absAdd = (+)
    absMul = (-)
    result = show

Felhasználása igen sokrétű lehet, használatához könnyű hozzászokni. Mivel más nyelvekben nincs ilyen szolgáltatás, hiányolja a hozzászokott programozó.

Több paraméteres osztályok

Ugyan még nem eleme a nyelvi szabványnak, de a jobb fordítóprogramok támogatják több paraméteres osztályok definiálásának lehetőségét.

class MultiParam a b where
    foo :: a -> b -> a

Monádok

Mint ahogyan arról már volt szó, a Haskell függvényei mellékhatás-mentesek. Ez azt jelenti, hogy a program környezete nem lehet hatással a programra, és fordítva. Környezet alatt értendő minden, ami nem szigorúan maga a program. Ilyen környezetben persze nem lehetne túl hasznos programokat írni, hiszen egy valamire való program folyamatos interakcióban van a környezetével. A másik probléma, hogy a lusta kiértékelés révén nem egyértelmű, hogy mi, milyen sorrendben hajtódik végre és ennek a sorrendnek a kikényszerítése, ha nem is megoldhatatlan, de problémás.

Haskellben ezeket a problémákat úgy orvosolták, hogy bevezették a kategória elméletből ismert monádokat. Ezek egyfelől a rajtuk végezhető operátorok segítségével kikényszerítik a sorrendiséget, másfelől a Haskell eszközeivel jól elkülönítik a mellékhatásos elemeket a mellékhatás-mentes elemektől.

Monádok használata

IO Monád

Nem minden Monád mellékhatásos. Mellékhatásosságot, csak az IO Monád enged meg. A jól ismert hello world program is mellékhatásos, hiszen kiírja, hogy "hello world!"

main :: IO ()
main = putStrLn "Hello World!"

monádokra jellemzőbb szintaxissal (előbbi akkor használatos, ha a monad egyetlen utasításból áll)

main = do
    putStrLn "Hello World!"

Ha több utasításunk van

main = do
    putStrLn "name?"
    name <- getLine
    putStrLn ("Hello " ++ name ++ "!")

Fontos kiemelni, hogy name nem egy változó, csak egy címke (pontosabban egy függvény paraméter (lásd: És ami mögötte van)). getLine típusa: IO String – Egy olyan IO Monad, mely egy String típusú számítást tárol. Ez a számítás mind annyiszor végrehajtódik, ahányszor futtatjuk.

Más IO Monádokat is be lehet emelni

main = do
    putStrLn "name?"
    name <- getLine
    printName name

printName :: IO ()
printName = do
     putStrLn ("Hello " ++ name ++ "!")
Maybe Monád

Maybe típus Preludben definiált

Maybe a
    = Nothing
    | Just a

Olyan esetekben alkalmazandó kényelmesen, ahol egy számításnak vagy létezik valamilyen eredménye, vagy nem. pl: [a] listából keressük ki az első f :: a -> Bool tulajdonságú elemet.

elem :: [a] -> Maybe a
elem [] = Nothing
elem (x:xs) = if f x then Just x else elem xs

Ha szükség van több Maybe eredményt visszaadó függvény kompozíciójára, a használata kényelmetlen lehet, a folyamatos mintaillesztések miatt.

foo :: Maybe a
foo = case getAList of
    Nothing -> Nothing
    Just l  -> case elem l of
        Nothing -> Nothing
        Just x -> case if x > 10 && x < 20 then Just x else Nothing of
            Nothing -> Nothing
            Just x -> doSomething x

Ezért a Preludeben, a Maybe példányosítva van, a Monad osztályra. Monádokkal a fenti függvény:

foo :: Maybe a
foo = do
    l <- getAList
    x <- elem l
    y <- if x > 10 && x < 20 then Just x else Nothing
    doSomething y

Ez a példányosítás pedig így néz ki:

instance Monad Maybe where
    (>>=) Nothing _   = Nothing
    (>>=) (Just v) f  = f v
    return            = Just

És ami mögötte van

A Monádok legalapvetőbb operátora a bind. Típusa

(>>=) :: m a -> (a -> m b) -> m b

ahol m a monád, a és b pedig monadikus számítások típusai.

Közelebbről: Két paraméteres függvény, első paramétere egy a monád, második paramétere egy függvény, ami a típusról képez b monádra. (>>=) operátor végrehajtja a monádot, majd az eredményét applikálja a második paraméterül kapott függvényre.

A Monádokat Haskellben egy osztály definiálja

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a

(>>) operátor szimplán kiszámolja szekvenciálisan két paraméterét. Olyan esetben alkalmazzuk, mikor a második monádhoz nem szükséges az első értéke. return kvázi becsomagol egy értéket, egy monádba. fail olyan esetekben hajtódik végre, amikor a bind második paraméterére applikálásakor mintaillesztési hiba történik. Nem szokás használni ezt a függvényt, sokan tervezési hibának tartják ezt az elemet.

A Haskell egy kényelmes szintaxist kínál monádok alkalmazására, ami kell is, hiszen látható, hogy (>>=) operátor közvetlen alkalmazása nem a legkényelmesebb. Ez a do szintaxis, ahogy az 'IO Monád' címkénél látható.

main = do
    putStrLn "name?"
    name <- getLine
    putStrLn ("Hello " ++ name ++ "!")

Átírása

main = (putStrLn "name?") >> (getLine >>= (\ name ->
          (putStrLn ("Hello " ++ name ++ "!"))))

Fajták

Haskellben a típusoknak is létezik típusa. Ezeket Fajtáknak (Kindnak) nevezzük.

A típusok fajtái a következőképpen kerülnek meghatározásra: A paraméter nélküli típusok egy *-osak. például Int :: * A paraméteres típusok annyi *-osak, ahány típus paraméterük van + 1. Például: Either :: * -> * -> *, de Either Bool Int :: *.

Erre a különbségtételre azért van szükség, mert Haskellben ezek egyáltalán nem átjárhatóak.

Jegyzetek

  1. [Haskell Announcing Haskell 2010], 2009. november 24. (Hozzáférés: 2023. január 11.)
  2. a b c d e f g h i j k l m Haskell 98 Report, p. xi
  3. John Backus. „Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs” (angol nyelven). [2007. június 21-i dátummal az eredetiből archiválva]. (Hozzáférés: 2015. április 13.)  

További információk

  • A Haskell programozási nyelv – részletes magyar nyelvű leírás, 2014.05.18., ELTE IK, Programozási Nyelvek és Fordítóprogramok Tanszék