module Monad from StdOverloaded import class zero (..), class + (..), class - (..) from StdOverloaded import class < (..), class / (..), class abs (..) from StdOverloaded import class length (..), class == (..), class * (..) from StdInt import instance + Int, instance < Int, instance - Int from StdInt import instance * Int, instance / Int, instance abs Int from StdInt import instance == Int from StdReal import instance / Real from StdList import sum, instance length [], flatten from StdTuple import fst, snd from StdFunc import o from StdString import instance +++ {#Char} import StdArray import StdBool import StdMisc import StdFile /* * Tegyük fel, hogy készíteni akarunk egy olyan tisztán funkcionális függvényt, amely * képes a külvilággal kommunikálni! A Clean nyelv esetében ez azt jelenti, hogy egy * olyan függvényt készítünk, amelyik megkapja a külvilágot egy állapotát, vagyis a * program környezetét, és miután ezt valamilyen módon megváltoztatta, továbbadja. * Ehhez egy olyan programot használunk illusztrációként, amely a következő lépésekből * áll: * * Írjuk ki a szabványos kimenetre, hogy "What is your name?". * Olvassunk be egy sort, egy nevet a szabványos bemenetről. * Ezután a beolvasott névből készítsünk egy köszöntést, vagyis írjuk vissza a * "Hello " előtaggal. * * Ennek a hagyományos módja a következő: */ program :: *World -> *World program world # (console, world) = stdio world # console = fwrites "What is your name? " console # (name, console) = freadline console # console = fwrites ("Hello " +++ name +++ "!\n") console # (_, console) = freadline console # (ok, world) = fclose console world | not ok = abort "Cannot close console" | otherwise = world /* * Ez a program erősen támaszkodik a `#` avagy "let before" jelölésre. Ennek * lényege, hogy törzs kiértékelése előtt még bizonyos részkifejezéseket * kiértékeltetünk. Ha több ilyen kifejezésünk van, akkor azok között így * tulajdonképpen egy sorrendet kötünk meg. Ezen keresztül egy szekvenciát * fektetünk le, ahol az egyes lépésekben a kezdetben paraméterként kapott * környezetet adogatjuk át. * * Egy ilyen függvényt viszont másképpen is fel tudunk írni. Itt a * programunkat több más, szintén a külvilággal kommunikálni tudó függvény * kompozíciójaként adjuk meg, az egész egyetlen nagy függvénykompozíció lesz, * ahol a résztvevő függvények egymásnak adogatják át a programkörnyezet * megváltoztatott állapotát. Ezért egy fejjel lefele olvasható programot * kapunk. Ehhez tehát a Clean függvénykompozíciós operátorát használjuk: * * (o) :: (b -> c) (a -> b) -> (a -> c) * (o) f g = \x -> f (g x) * * Az utolsó függvényben a `getLine` eredményét dolgozzuk fel egy (névtelen) * lambda-függvénnyel, ahol a kapott értékre, egy rendezett párra illesztünk mintát. * Erre azért van szükség, mert a `getLine` valójában nem egy, hanem két értéket ad * vissza: ugyanis a programkörnyezet megváltoztatott állapota mellett megkapjuk azt a * sort is, amelyet kiolvastunk belőle. */ program0 :: *World -> *World program0 world = ((\(name,world) -> ((\(_, world) -> world) o getLine o putStr ("Hello " +++ name +++ "!\n")) world) o getLine o putStr "What is your name?") world /* * A rend kedvéért megadjuk a `putStr` és `getLine` definíciót is a Clean eszközeinek * segítségével. A hatékonyabb kiértékelést a uniqueness annotáció (*) segíti a * típusban, amelynek köszönhetően a "let before" (#) kifejezésekben a bal oldalon * szereplő neveket nem kell indexelni, mindig hívhatjuk ugyanúgy a változót, és ezáltal * felül tudjuk írni az értékét. */ putStr :: String *World -> *World putStr s w # (c, w) = stdio w # c = fwrites s c # (ok, w) = fclose c w | not ok = abort "Cannot close console" | otherwise = w getLine :: *World -> (String, *World) getLine w # (c, w) = stdio w # (s, c) = freadline c # (ok, w) = fclose c w | not ok = abort "Cannot close console" | otherwise = (s,w) /* * A programban szereplő utasítások sorrendjét a kompozíció operátorának * megváltoztatásával könnyen helyre tudjuk tenni. Ehhez mindössze annyit csináltunk, * hogy készítettünk egy `|>` operátort, amely megfordítja a kompozíció irányát. */ program1 :: *World -> *World program1 world = (putStr "What is your name?" |> getLine |> (\(name,world) -> (putStr ("Hello " +++ name +++ "!\n") |> getLine |> (\(_,world) -> world)) world)) world (|>) infixl 0 :: (.a -> .b) (.b -> .c) -> (.a -> .c) (|>) f g = \x -> g (f x) /* * De hogy ne kelljen a `World` típusú értékeket sem magunknak folyamatosan átadni a * programon belül (ez ugyanis rengeteg hibalehetőséget rejt magában), létrehozzuk * az `IO` típust, amely egy speciális függvénytípus. Ezzel ábrázoljuk azt, hogy a * program környezetét átvisszük egyik állapotából a másikba, miközben elő tudtunk * állítani egy tetszőleges `a` típusú értéket. */ :: IO a :== *World -> *(a, *World) /* * Vannak természetesen olyan esetek, amikor nem akartunk semmilyen eredményt * előállítani, egyedül az állapotváltásra volt szükségünk. Ezért erre a célra * definiáltuk a `Unit` (egység)típust, amelynek egyetlen eleme van, a `Unit`. Ez a * hagyományos nyelvek `void` (visszatérési érték nélküli függvény) feleltethető meg. */ :: Unit = Unit /* * Emiatt egy kicsit meg kell változtatnunk a `putStr` függvény eddigi típusát, * ugyanis az nem teljesen ilyen alakú: nem párt ad vissza, hanem csak a környezet * megváltoztatott állapotát. Ez továbbra is így marad, csak annyival kell még * kiegészítenünk, hogy a számítás eredménye `Unit` lesz. */ putStrM :: String *World -> (Unit, *World) // avagy: String -> IO Unit putStrM s w # (c, w) = stdio w # c = fwrites s c # (ok, w) = fclose c w | not ok = abort "Cannot close console" | otherwise = (Unit, w) /* * Az `IO a` típusú értékeket I/O "akcióknak" nevezzük. Ezek lényegében olyan * műveletek, amelyek kiszámítanak egy `a` típusú eredményt, azonban lehet * `IO` típusú mellékhatásuk. Vagyis elképzelhető, hogy a működésük * eredményeképpen megváltoztatják a program környezetét, például kiírnak * valamit a szabványos kimenetre. * * Tiszta funkcionális nyelvekben viszont minden függvény csak annyit * csinálhat, amit a típusa is megenged. Ha az `IO` nem szerepelne a típusban, * akkor valójában konstans értékekről beszélünk, mivel nem függ semmilyen * értéktől. * * Ezzel szemben az `IO` azt teszi lehetővé, hogy minden egyes esetben újra * és újra kiértékeljük a számítást, így akár esetenként eltérő eredményt * kapjunk. Ezt természetesen egy tiszta nyelvben elég körülményesen lehet * elérni, hiszen ahogy már korábban is láthattuk, ilyenkor mindig adogatnunk * kellene a megváltoztatható környezetet, így ezt a megoldást használtuk fel * arra, hogy mindezt rejtetté tegyük. * * Figyeljük meg azt is, hogy mivel az `IO a` valójában egy függvénytípust * takar, a függvény eredménye is egy másik függvény kell, legyen. Ez egy * egyparaméteres (lambda-)függvény, amely a programkörnyezet aktuális * állapotát tartalmazza, ezzel tudunk dolgozni (ha szükség lenne rá). * * Viszont gondoskodnunk kell arról, hogy két `IO` akciót egymás után is * lehessen kapcsolni, ezáltal nagyobb `IO` akciókat építeni belőlük. Ez az * az ún. "bind" művelet, amelyet itt most a `|>>=` operátorral adtunk meg. * A "bind" műveletnek az a szerepe, hogy az első `IO` akció `a` típusú * eredményét át tudja adni az utána következő, második, `b` típusú értéket * kiszámító `IO` akciónak és ezzel egy olyan `IO` akciót hozzon létre, amely * azt a `b` típusú értéket számítja ki. * * Ezt úgy érjük el, hogy lefuttatjuk az első akciót a programkörnyezet * aktuális állapotával (átadjuk a számításban levő függvénynek a hiányzó * paraméterét). Ebből aztán megkapjuk az első akció eredményét, illetve a * programkörnyezet (potenciálisan) megváltozott állapotát. Ezek * felhasználásával tudjuk aztán a következő akciót lefuttatni és így a * végeredményt megkapni. Figyeljük meg, hogy itt is végig egyetlen * (lambda-)függvényt szerkesztettünk meg. * * A definícióban a "let" kulcsszó ugyanazt a célt szolgálja, mint a "where", * csak ebben az esetben a kifejezésben használni kívánt neveket előre * definiáljuk. A szintaktikája ennek megfelelően lényegében a következő: * * let x = e in k * * Ahol "x" a definiálandó név (amely egyébként minta, tehát ott a * mintaillesztés szabályai is alkalmazhatóak), az "e" annak értéke, * az "in" utáni rész pedig, ahol a definiált nevet ("x") fel tudjuk * használni az "e" értékkel. */ (|>>=) infixl 1 :: (IO a) (a -> IO b) -> IO b (|>>=) m k = \w -> let (x,w1) = m w in k x w1 /* * Előfordulhatnak olyan esetek, amikor az első akció eredményét figyelmen kívül * akarjuk hagyni (mivel például csak egy `Unit` értéket adnának vissza). Erre * hoztuk létre a `|>>=` egy specializált változatát, a `|>>` operátort, amely * ezt írja le. */ (|>>) infixl 1 :: (IO a) (IO b) -> IO b (|>>) m k = m |>>= \_ -> k /* * A programunkat ezzel az absztrakcióval az alábbi módon lehet megfogalmazni: */ program2 :: *World -> *World program2 world = snd (runIO main world) where main :: IO Unit main = putStrM "What is your name? " |>> getLine |>>= \name -> putStrM ("Hello " +++ name +++ "!\n") |>> getLine |>>= \_ -> returnIO Unit /* * A `|>>=` és `|>>` mellett megjelent még egy "return" nevű művelet, amellyel * mellékhatással nem rendelkező értéket emelhettünk be az `IO` számítások * közé. Vegyük észre, hogy ez nem azonos az imperatív nyelvek esetén * megszokott `return` művelettel! Ennek a definíciója a következő: */ returnIO :: a -> IO a returnIO x = \w -> (x, w) /* * Láthatjuk, hogy a `return` esetében a kapott programkörnyezettel (`w`) * nem csináltunk semmit, változatlanul továbbadjuk. * * Végezetül szerepelt egy futtató függvény is az `IO a` típusú értékekhez. * Ez a függvény, amely kiszámítja az akció értékét, itt lehet megadni a * programkörnyezet kezdőállapotát, amellyel lejátssza a számítást. */ runIO :: (IO a) *World -> *(a, *World) runIO action w = action w /* * Ez, a korábbiakban alkalmazott strukturáló eszköz nem csak I/O műveletek * egyszerűbb leírása esetén bizonyulhat hasznosnak, hanem bármilyen olyan * esetben, amikor a számításunk valamilyen állapottal dolgozik. * * Ezért, ha az `IO` típusban a `World` típust egy `s` paraméterre cseréljük, * akkor kaphatunk egy olyan típust, amely képes tetszőleges állapotátmenet * leírására. Ez lesz a kétparaméteres `S`, avagy `State` típus: * * S :: * -> * -> * * * Ennek megfelelően aztán hozzá tudjuk igazítani a korábbi, `IO` típusra * vonatkozó definícióinkat. Sajnos, mivel a `|>>=` és a többi név már * foglalt, ezért másképpen kell elneveznünk ezeket. Ennek a problémának a * megoldásával hamarosan foglalkozni fogunk. */ :: S s a :== s -> (a, s) return_S :: a -> S s a return_S x = \s -> (x, s) (bind_S) infixl 1 :: (S s a) (a -> S s b) -> S s b (bind_S) m k = \s -> let (x,s1) = m s in k x s1 (then_S) infixl 1 :: (S s a) (S s b) -> S s b (then_S) m k = m bind_S (\_ -> k) runS :: (S s a) s -> (a, s) runS action s = action s /* * Mivel az `S` típust az `IO` általánosításából származtattuk, lényegében * vissza is tudjuk kapni belőle: :: IO a = S World a * Emlékezzünk azonban még vissza, hogy az `IO` típushoz kapcsoltunk még * további műveleteket is (`putStr`, `getLine`)! Ezek segítségével tudtunk * ugyanis a szabványos bemenetről beolvasni, valamint a szabványos kimenetre * kiírni. Ezeket az előbbi általánosítás nem érintette, az `S` típushoz most * megadjuk a saját műveleteit. * * Ezek közül az első a `get`, amely arra szolgál, hogy az akcióban az * implicit állapotot le lehessen kérdezni. Ezt az `IO` esetében nem engedtük, * helyette a hozzárendelt műveletek tudták csak módosítani. */ get_S :: S s s get_S = \s -> (s, s) /* * A másik ilyen művelet a `put`, amellyel az implicit állapotot tudjuk a * paraméterül megadott értékkel felülírni. Mivel a számítás eredménye ekkor * `Unit` lesz, tehát ez egy mellékhatásos művelet. */ put_S :: s -> S s Unit put_S x = \s -> (Unit, x) /* * Az előbbiek segítségével készíthetünk például egy `fromTo` akciót, amely a * listák esetén megismert `..` ("pont-pont") kifejezésnek felel meg: vagyis * az a feladata, hogy egy értéktől (mint alsó korláttól) elindulva építsen * listát addig az egyesével növekvő elemekből, amíg el nem éri a másik értéket * (mint felső korlátot). Vagyis: * * [a..b] = fromTo a b * * Itt alapvetően egy rekurzív függvényt készítünk, amely egy `Int` értékekből * álló párt használ állapotként és eredményül `Int` értékek listáját készíti * el. Az imperatív nyelvekből kölcsönzött szintaktikával az alkalmazott * algoritmus nagyjából a következő: * * (Int,Int) s; // globális változó (állapot) * * [Int] f() { * (n,m) := s; // get * if (n >= 0) { * s := (n - 1, m + 1); // put * xs := f(); * return [m:xs]; * } * else return []; * } */ fromTo_S :: Int Int -> [Int] fromTo_S x y = fst (runS f (y - x, x)) where f :: S (Int,Int) [Int] f = get_S bind_S \(n,m) -> if (not (n < 0)) (put_S (n - 1, m + 1) then_S f bind_S \xs -> return_S [m:xs]) (return_S []) // Start = fromTo_S 1 10 /* * Fentebb már említettük, hogy hasznos lenne, ha ugyanazokat a jelöléseket * használhatnánk a "bind" és a többi művelet esetén. Ez lényegében azt * igényli, hogy képesek legyünk túlterhelni a jelöléseket, vagyis ezt egy * megfelelő típusosztály létrehozásával át tudjuk hidalni. * * A fentebb bemutatott struktúrát monádnak hívják, ezért az osztály ezt a * nevet kapja. Vegyük észre, hogy a típusosztály paramétere egy olyan * típusváltozó lesz, amelynek meg kell adni egy másik típust paraméterként * ahhoz, hogy használni tudjuk. Emiatt az `m` paraméter "típusa", vagyis * kindja a következő lesz: * * m :: * -> * * * és emiatt a `Monad` osztályt nem egyszerűen típusosztálynak, hanem * típuskonstruktor-osztálynak nevezzük. A `Monad` ugyanis nem egyszerűen * egy típus felett terheli túl a műveleteket, hanem egy magasabbrendű * típus, vagyis egy típuskonstruktor felett. * * Ha megnézzük, akkor az `IO` és `S` típusok lényegében ilyenek voltak. * A túlterhelt műveletek típusát is ezeknek a kitörlésével kaptuk: * * return :: a -> m a * (>>=) :: (m a) (a -> m b) -> m b * * A típusosztályok alkalmazásának egy másik előnye, hogy a `>>` műveletet * már meg sem kell adnunk, mivel a típusa mellett a definícióját is tudjuk * származtatni a `>>=` definíciójából. */ class Monad m where return :: a -> m a (>>=) infixl 1 :: (m a) (a -> m b) -> m b (>>) infixl 1 :: (m a) (m b) -> m b (>>) m k :== m >>= \_ -> k /* * A típusosztályok alkalmazásának azonban ára is van. Ne feledjük ugyanis, * hogy az `IO` és `S` típusok nem valódi típusok voltak, hanem csupán * szinonimák! Ez azt jelenti, hogy amikor definiálni akarjuk ezeket mint a * `Monad` osztály példányait, valójában az `a -> b` (függvény)típust akarjuk * több különböző formában példányként megadni. * * Ez azért jelent gondot, mert az alkalmazandó példányt a típus alapján * határozzuk meg, a túlterhelés feloldása, vagyis annak megállapítása, hogy az * adott helyen ténylegesen melyik definíciót kell alkalmazni, nem lesz * egyértelmű. Ezt a jelenséget átfedő típusosztály példányok, avagy * "overlapping instances" néven ismerik. * * Ezt a határozatlanságot úgy tudjuk kiküszöbölni, ha az `IO` és `S` * korábbi definícióit szinonimákból különálló típusokká alakítjuk. Ezt az * átalakítást csomagolásnak ("wrapper") nevezzük. Általánosan leírva ez a * következőt jelenti. * * Tegyük fel, hogy a `T` típust akarjuk csomagni az `W` típusba. Ekkor a * `W` definíciója az alábbi: * * :: W = WR T * * így kapunk egy `WR` függvényt (mint a `W` adatkonstruktora), amellyel a * `T` típusú értékeket `W` típusává alakíthatjuk: * * WR :: T -> W * * Kell viszont egy kicsomagoló függvény is, amely a `W` értéket visszaalakítja * `T` típusúvá: * * unW :: W -> T * unW (WR t) = t * * Ennek a technikának köszönhetően a `State` típussal be tudjuk csomagolni az * `S` típust, és ezzel megadni a `Monad` osztály példányát. */ :: State s a = ST (S s a) unST :: (State s a) -> S s a unST (ST m) = m /* * Viszont azt észrevehetjük, hogy a `State` egy kétparaméteres típus, miközben * a `Monad` osztály egyparaméteres típusokat vár. Szerencsére ez nem okoz * gondot, mivel a típusok kindjai és curry-zhetőek, hasonlóan a függvények * típusaihoz. Vagyis a `State` kindja így is felírható: * * State :: * -> (* -> *) * * Tehát, ha a `State` első paraméterét megadjuk, akkor pontosan a megfelelő * kindú típust kapjuk: * * State s :: * -> * * * Ez egyben azt is jelenti, hogy a `State` önmagában még nem monád, hanem egy * absztrakt monád, amely az állapot típusával, `s`-sel, paraméterezhető. */ instance Monad (State s) where return x = ST (return_S x) (>>=) m k = ST ((unST m) bind_S (\x -> unST (k x))) /* * Ne felejtsük, hogy a korábban már társított műveleteinket is át kell alakítani * a csomagolásnak megfelelően. */ get :: State s s get = ST get_S put :: s -> State s Unit put x = ST (put_S x) runState :: (State s a) s -> (a, s) runState action s = runS (unST action) s /* * A `State` esetén hasznos lehet a futtató függvény mellett megadni annak egy * változatát, ahol a számítás végén az eredményül keletkező végállapotot * eldobjuk. Ez az `evalState`. A másik lehetőség az, amikor a számítás * eredményét hagyjuk a futtatás után, ezt `execState` néven szokták * definiálni. */ evalState :: (State s a) s -> a evalState a s = fst (runState a s) /* * A `State s` `Monad`-példány megadása után most valamivel olvashatóbb lett a * `fromTo` akció definíciója, de igazából ugyanaz, mint korábban. */ fromTo :: Int Int -> [Int] fromTo x y = evalState f (y - x, x) where f :: State (Int,Int) [Int] f = get >>= \(n,m) -> if (not (n < 0)) (put (n - 1, m + 1) >> f >>= \xs -> return [m:xs]) (return []) // Start = fromTo 0 10 /* * Léteznek még további monadikus strukturák is, ilyen többek közt a korábban * megismert `Maybe` típus is. Ez is egy típuskonstruktor (tehát kindját * tekintve megfelelő), de emellett megadhatóak hozzá a `return` és a `>>=` * definíciói úgy, hogy azzal egy mellékhatást írjunk le. * * Ez a mellékhatás a számítás eredményének opcionalitása, vagyis így tudjuk * leírni, hogy a számításnak nem feltétlenül lesz eredménye, parciális. A `Maybe` * alkalmazásával lényegében totálissá alakítjuk ezeket a függvényeket, tehát mindig * lesz eredményük. Ott, ahol a függvény az adott pontban mégsem volt értelmezhető, * a `Nothing` értéket adjuk vissza, amely nem eleme az eredmény típusának. Ezért * egyértelműen jelzi, amikor a számításnak nincs eredménye. * * Továbbá az ilyen parciális számításokat sorba is kapcsolhatjuk: a rákövetkező * számításokat csak abban az esetben hajtjuk végre, ha van eredmény. Ellenkező * esetben az egész számítási lánc megszakad, nagyjából ahhoz hasonlóan, amikor egy * kivétel keletkezik. Ez viszont így nem feltétlenül jár a programot ábrázoló * lambda-kifejezés kiszámításának megszakadásával. */ :: Maybe a = Just a | Nothing instance Monad Maybe where return x = Just x (>>=) (Just m) k = k m (>>=) _ _ = Nothing /* * A `Maybe` mellékhatásának szemléltetésére használjuk a `safeDiv` függvény * korábbi definícióját: ha nullával akarunk osztani egy egész számot, akkor * az eredmény `Nothing`, egyébként az eredmény `Maybe` típusba csomagolt * változata. */ safeDiv :: Int Int -> Maybe Int safeDiv _ 0 = Nothing safeDiv x y = Just (x / y) /* * Ez a számítást felhasználjuk egy nagyobb számítás részeként, ahol egy lista * elemeinek átlagától való átlagos eltérését akarjuk kiszámolni. A típusából * megfigyelhetjük, hogy a `Maybe` típus terjed, mivel a befoglaló számítás * típusában is megjelenik. * * Hasonlóan a `fromTo` számítás korábbi leírásához, az `averageDeviation` * definícióját is megadhatjuk pszeudókóddal: * * (Maybe Int) averageDeviation ([Int] xs) { * (Maybe Int) average ([Int] xs) { * result := safeDiv (sum xs) (length xs); * return result; * } * * mean := average(xs); * result := (average [ abs(x - mean) \\ x <- xs ]); * return result; * } * * A fenti vázlatban a `return` hívást odaraktuk a törzsek végére, hogy * látszódjon, mi lesz az eredménye, de ahogy majd később láthatjuk, ezeket a * sorokat mindig össze lehet vonni a monadikus számításokban. Illetve azt is * láthatjuk, hogy az egyes akciókat itt is pontosvesszőkkel választottuk el * egymástól. Ezek tulajdonképpen a `>>=` és `>>` operátoroknak feleltethetőek * meg. Ezért is szokták a "bind" műveletet programozható pontosvesszőnek is * nevezni, mivel a `Monad` példány megadásakor ennek a (denotációs) * szemantikáját írjuk le. * * Az `averageDeviation` függvényben tehát, ha valamelyik pontban a `safeDiv` * nullával osztana, vagyis `Nothing` értéket adna vissza, akkor az egész * számításnak az eredménye is az lesz. A kivételkezelésnél megszokottakhoz * hasonlóan ezért nem kell minden egyes hívás után megvizsgálni a visszatérési * értéket, hanem egyszerűen csak úgy kell leírnunk az egész algoritmust, * mintha nem is fordulhatna elő ilyen eredmény. * * Az `average` függvény egy alfüggvény, amelyet a `let` utasítással hozunk * létre a monadikus blokkban. Ilyen, és hasonló definíciókat bármikor meg * tudunk adni. Ez a "bind" mellékhatásmentes alternatívája, amivel * rövidítéseket vezethetünk be. */ averageDeviation :: [Int] -> Maybe Int averageDeviation xs = let average xs = safeDiv (sum xs) (length xs) in average xs >>= \mean -> average [ abs (x - mean) \\ x <- xs ] // Start = (averageDeviation (fromTo 1 10), averageDeviation []) /* * A `Maybe` típus mellett a lista típusára, a `[]` típusra is felírható egy * monadikus példány. Vagyis, listák segítségével is lehet ábrázolni * monadikus műveleteket. Ebben az esetben a mellékhatás az lesz, hogy egy * monadikus akciót egyszerre több elemen végzünk el, majd ezeket újra * egyetlen listává kombináljuk össze. Nézzük meg a lista esetében a "bind" * definicióját! */ instance Monad [] where return x = [x] // (>>=) :: [a] (a -> [b]) -> [b] (>>=) m k = flatten [ k x \\ x <- m ] /* * Erre példa a `multiplyTo` számítás, amely (mezítlábas módszerrel) megadja, * hogy egy egész szám milyen másik két egész szám szorzataként állítható elő. * * Pszeudókód helyett most egy másik összefüggésre világítunk rá: az így * megadott akciók (a `Monad` példány definíciójából adódóan) valójában * listakifejezések segítségével is felírhatóak. A `multiplyTo` például így * adható meg egyetlen sorban mint listakifejezés: * * multiplyTo n = [ (x,y) \\ x <- [1..n], y <- [x..n] | x * y == n ] */ multiplyTo :: Int -> [(Int,Int)] multiplyTo n = fromTo 1 n >>= \x -> fromTo x n >>= \y -> if (x * y == n) (return (x, y)) [] // Start = multiplyTo 100 /* * Amikor definiálunk egy monadikus struktúrát, akkor a `return` és `>>=` * definícióinak még további megszorításoknak is eleget kell tenniük. Ezeket * a típusrendszer segítségével nem tudjuk automatikusan garantálni, mindig * magunknak kell megvizsgálni. * * A megszorítások, vagy másnéven a monádtörvények, megadásához bevezetünk * egy segédfüggvényt. Ez az `>=` operátor, az ún. Kleisli-féle kompozíció * művelete. Láthatjuk, hogy típusát tekintve ez hasonlít a `>>=` művelethez, * továbbá ki is fejezhető azzal. Azért vezetjük be, mert így jobban hasonlít * a hagyományos függvényekre, két eltéréssel: a kompozíció fordítva * tartalmazza a részfüggvényeket, illetve a részfüggvények mindegyikének lehet * mellékhatása (ezt jelzi az `a -> m b` típus). */ (>=>) infixr 1 :: (a -> m b) (b -> m c) -> (a -> m c) | Monad m (>=>) f g = \x -> f x >>= g /* * Ennek segítségével most már felírhatjuk a törvényeket: * * return >=> m === m >=> return === m (egységelem) * (f >=> g) >=> h === f >=> (g >=> h) (asszociativitás) * * A törvények egyik lehetséges alkalmazása a monadikus kompozíciók * egyszerűsítése és optimalizálása. Ezt a fordítóprogramok is * kihasználhatják, ezért is fontos a monadikus struktúrának teljesítenie * ezeket. */ Start = 42