Haskell (programozási nyelv)
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
szerkesztésA 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
szerkesztésTípusok
szerkesztésA 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
szerkesztésImperatí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
szerkesztésA 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
szerkesztésA 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
szerkesztésA 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
szerkesztésEz 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
szerkesztésCurry-jelölés
szerkesztésA 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
szerkesztésA 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
szerkesztésA 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
szerkesztésA 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
szerkesztésHaskellben, (é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
szerkesztésHa 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
szerkesztésHaskellben 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
szerkesztésUgyan 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
szerkesztésMint 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
szerkesztésIO Monád
szerkesztésNem 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
szerkesztésMaybe 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
szerkesztésA 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
szerkesztésHaskellben 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
szerkesztés- ↑ [Haskell Announcing Haskell 2010], 2009. november 24. (Hozzáférés: 2023. január 11.)
- ↑ a b c d e f g h i j k l m Haskell 98 Report, p. xi
- ↑ 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
szerkesztés- 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