A lista egy rendkívül hasznos adatstruktúra. Csakúgy mint a legtöbb funkcionális programozási nyelvben a listának kitüntetett a szerepe az ML -ben. A lista az ML -ben olyan mint egy láncolt lista a C -ben vagy a PASCAL -ban, de a mutatók bonyolult kezelése nélkül. Egy lista ugyanolyan típusú elemek sorozata. Kétfajta lista konstruktor létezik: az üres lista (nil és a cons operátor "::". A nil konstruktorral üres listákat hozhatunk létre. A "::" operátor bal oldalán egy elem szerepel, jobb oldalán egy lista, amiből az eredeti listánál egyel hosszabb listát hoz létre. Példák:
| nil | [ ] |
| 1::nil | [ 1 ] |
| 2::(1::nil) | [ 2,1 ] |
| 3::(2::(1::nil)) | [ 3,2,1 ] |
Valójában a cons operátor jobbra asszociatív, így a zárójelek nem szükségesek. Egyszerűen írhatunk 3::2::1::nil -t a [ 3, 2, 1 ] lista létrehozásához. Megfigyelhetjük, hogy a "::" mindig egy elem és egy lista között áll. Az "::" operátort használhatjuk arra, hogy egy elemet adjunk egy lista fejéhez. A "@" operátort használhatjuk listák összefűzésére. Gyakran elkövetett hiba, hogy összekeverik az egy elemet tartalmazó listát egy elemmel. Például a 4 -et hozzávehetjük a [ 5, 6, 7 ] lista elejére a "::" operátorral: 4 :: [ 5, 6, 7 ] vagy írhatjuk azt, hogy [ 4 ] @ [ 5, 6, 7 ]. A 4 @ [ 5, 6, 7 ] és a [ 4 ] :: [ 5, 6, 7 ] hibát okoz. A 4 -et a lista végére szeretnénk rakni, nem írhatjuk azt, hogy [ 5, 6, 7 ] :: 4 csak azt, hogy [ 5, 6, 7 ] @ [ 4 ]. (Aminek az eredménye [ 5, 6, 7, 4 ].)
Lista utolsó eleme
Amikor listákon értelmezet függvényeket definiálunk általában a következő két mintát használjuk:
fun lfun nil = ...
| lfun(h::t) = ... lfun t ...;
Azonban nem szükségszerűen mindig ez az eset. Vegyük például a last függvényt, amely egy lista utolsó elemét adja vissza:
last [4,2,5,1] = 1
last ["sydney","beijeng","manchester"] = "manchester"
A "szokásos" két minta nem jó erre az esetre. Vegyük például az üres lista utolsó elemét. Mi egy üres lista utolsó eleme?? Ez egy olyan egyszerű kérdés, mint a "mi egy üres lista szorzata?". A "last nil" kifejezésnek nincs értelmes értéke, ezért legjobb, ha nem definiáltnak hagyjuk. Tehát ahelyett, hogy a szokásos módon egy nulla hosszú listából indulnánk ki, most egy 1 hosszú listából fogunk kiindulni. A [h] minta illeszkedik minden olyan listára, amely pontosan egy elemet tartalmaz.
fun last [h] = h
| last(h::t) = last t;
Ennek a függvénynek két speciális tulajdonsága is van, a nem-teljesség és a minták átfedése.
Listák összege
Készítsünk egy függvényt, amely egy lista összes elemét összeadja:
sum [2,3,1] = 2 + 3 + 1 = 6
Két alapvető minta létezik listákhoz - mivel kétfajta listakonstruktor van (:: és a nil). A "::" szimbólumot cons -nak hívják, és két komponense van, a nil egy üres listát csinál. Mindkét fajta konstruktorhoz írhatunk egyenleteket (mintaillesztéshez). Az üres listára könnyű elkészíteni az összegző függvényünket, mivel üres lista összege definíció szerint nulla:
sum nil = 0
A cons konstruktor esetében a lista fejelemét (h, mint head) hozzá kell adnunk a maradék lista (t, mint tail) összegéhez. Ez egy rekurzív függvény lesz. A rekurzió terminálása biztosított, mivel egyre kisebb méretű listákra hívjuk meg a sum függvényt, és üres listákra már definiáltuk a függvényt. A teljes sum függvény:
fun sum nil = 0
| sum(h::t) = h + sum t;
Listák összefűzése
A infix @ egy előre definiált függvény, de mi is levezethetnénk a definícióját a következőképpen: az összefűzés (@) operátor két listát kapcsol össze, például:
[1,2,3] @ [4,5,6] = [1,2,3,4,5,6]
Mivel két paraméterünk van, és mindkettő lista, választhatunk, hogy melyik szerinti rekurziót alkalmazunk. Ha a második paraméter szerinti rekurziót alkalmazunk, a függvény (a jobb oldalak nélkül) így fog kinézni:
fun x @ nil = ??
| x @ (h::t) = ??;
Ez azonban nem bizonyul hasznos definíciónak, így az első paraméter szerinti rekurziót fogunk alkalmazni:
fun nil @ x = ??
| (h::t) @ x = ??;
Az első egyenlet könnyű, mivel, ha az üres listát fűzzük össze egy másik listával, az eredmény egyszerűen a másik lista lesz. A második egyenlet egy kicsit komplikáltabb. Az első listát (h::t) a második (x) lista elé kell helyeznünk. Ezt úgy kaphatjuk meg, ha h -t cons -oljuk (a cons vagy :: operátorral egy elemet tudunk egy lista elejére rakni), a maradék (t) lista és x összefűzésével kapott listához. A @ definiálásához felhasználtuk a @ definícióját is, tehát ez is egy rekurzív definíció:
fun nil @ x = x
| (h::t) @ x = h::(t @ x);
Megjegyzés: Természetesen a @ operátor előre definiált (predefined) operátor. A @ operátor tényleges definíciója egy kicsit bonyolultabb annál, mint amit itt levezettünk.
Doublist
Nézzünk egy függvényt, amely a paraméterül kapott lista összes elemét megduplázza:
doublist [5,3,1] = [10,6,2]
Ismét két esetet fogunk kezelni: a nil -t és a (h::t) -t. Az alapeset a nil:
doublist nil = nil
A leggyakoribb hiba azt hinni, hogy doublist nil az 0. Ha csak a típusokra figyelünk, akkor is látjuk, hogy ez értelmetlen lenne, mivel a doublist kimenetének listának kell lennie, és nem egy egész számnak. A cons (::) esetében egyszerűen a fejelem (h) dupláját hozzáfűzzük a maradék lista (t) doublist -jéhez.
doublist(h::t) = 2*h :: doublist t
Map
Megfigyelhetjük, hogy sok rekurzív függvényben ugyanazok a minták szerepelnek. A következő függvények megdupláznak ill. megnövelnek minden elemet egy listában:
fun doublist nil = nil
| doublist(h::t) = 2*h :: (doublist t);
fun inclist nil = nil
| inclist(h::t) = (h+1) :: (inclist t);
Tipikus végrehajtások:
doublist [1,2,3,4] = [2,4,6,8]
inclist [1,2,3,4] = [2,3,4,5]
Természetesen alkalmazhatunk absztrakciót, és írhatunk egy függvényt, amely egy tetszőleges függvényt alkalmaz egy lista elemeire, ez a map:
fun map f nil = nil
| map f (h::t) = (f h)::(map f t);
A map segítségével alternatív definíciót adhatunk a doublist és az inclist függvényekre:
val doublist = map (fn x=>2*x);
val inclist = map (fn x=> x+1);
Reduce
A reduce függvénynek három bemenete van: egy bináris (két argumentumú) függvény, egy kezdőérték és egy lista. A megadott listára ismétlődve alkalmazza a függvény a kezdőértéktől kezdve. Például:
reduce f b [i1, i2, i3] = f(i1, f(i2, f(i3, b)))
Figyeljük meg a kapcsolatot a sum és a flatten függvényekkel. (A flatten függvény listák listájából csinál egy sima listát).
fun sum nil = 0
| sum(h::t) = h + sum t;
fun flatten nil = nil
| flatten (h::t) = h @ flatten t;
Tipikus végrehajtások:
sum [10, 20, 30] = 60
flatten [[1,2],[3,4],[5,6,7]] = [1,2,3,4,5,6,7]
Ezeket megvalósíthatjuk a reduce minta segítségével is - van egy kezdőértékünk az üres listára, a cons -ra pedig alkalmazzuk a bináris függvényünket a fejelemre és a rekurzív hívás eredményére:
fun reduce f b nil = b
| reduce f b (h::t) = f(h,reduce f b t);
Ezután újradefiniálhatjuk a sum és a flatten függvényeket:
val sum = reduce (fn(a,b)=>a+b) 0;
val flatten = reduce (fn(a,b)=>a@b) nil;
Valójában még ennél is jobbat tehetünk: az ML megengedi, hogy átalakítsuk az infix függvényeket, mint a milyen a + vagy a @ prefix függvényekké az op kulcsszó segítségével:
reduce (op +) 0 [1,2,3,4];
reduce (op @) nil [[1,2],[3,4],[5,6,7]];
Fold
Az előre definiált fold függvény ugyanaz mint a reduce csak az argumentumok más sorrendben szerepelnek. A reduce–t így is definiálhatjuk.
fun reduce f b l = fold f l b;
Zip
A zip -et arra használhatjuk, hogy egy két változós (bináris) függvényt alkalmazunk két listára, például:
zip (op +) [1,2,3] [2,4,6] = [3,6,9]
A zip a következőképpen van definiálva:
fun zip f nil nil = nil
| zip f (h::t) (i::u) = f(h,i)::zip f t u;
Filter
A filter egy predikátumból (olyan függvényből ami igazat vagy hamisat ad vissza) és egy listából egy olyan listát állít elő, amelyben a lista csak azon elemei szerepelnek, amelyre a predikátum igaz. Például nézzük a páros (even) függvényt:
fun even n = (n mod 2 = 0);
most alkalmazzuk a filter függvényt az [1, 2, 3, 4, 5, 6] listára.
filter even [1,2,3,4,5,6] = [2,4,6]