Lusta kiértékelés és végtelen listák
A Miranda kiértékelő mechanizmusa úgynevezett lusta kiértékelés. Ez pontosan azt jelenti hogy semelyik alkifejezés nem értékelődik ki mindaddig, míg nincs szükség az értékére. Egyik következménye mindennek, hogy így lehetséges kötetlen függvények definiálása, azaz ezek a függvények képesek értéket visszadni akkor is, ha valamelyik argumentumuk nem definiált. Másik lényeges következménye a lusta kiértékelésnek, hogy lehetőve teszi végtelen adatszerkezetek definiálását. Lássuk néhány végtelen lista definícióját (melyekben a végtelen számtani sorozatok jelölésére a .. jelölés egy módosított alakját láthatjuk): ones = 1 : ones
repeat a = x
where x = a : x
nats = [0..]
odds = [1,3..]
squares = [n*n | n<-[0..]]
perfects = [n | n<-[1..]; sum(factors n) = n]
Például az Eratosztenészi szitát megvalósító program prímszámok végtelen listáját adja
eredményül. Először a gen függvényt definiáljuk, mely az [n,n+1,...] végtelen listát generálja: gen:: num->[num]
gen n = n : gen (inc n)
A filter (szűrő) két argumentummal rendelkezik: egy számmal és egy (akár végtelen) listával.
A filter eltávolítja az adott szám minden többszörösét a listából: filter:: num->[num]->[num]
filter pr (hd : tl) = hd : filter pr tl, hd mod pr ~=0
= filter pr tl, otherwise
A sieve (szita) a prímek egy végtelen listáját fogja eredményezni feltéve, ha a végtelen
lista első eleme prím. A függvény rekurzívan hívja önmagát, és kiszűri a talált prím minden többszörösét
az input listából: sieve:: [num]->[num]
sieve (pr : rest) = pr : sieve (filter pr rest)
Az a kezdeti kifejezés, mely az összes prímet tartalmazó végtelen listát fogja eredményezni a következô: sieve(gen 2)
Ha egy függvény kiértékelése lusta kiértékelési sémával van végrehajtva, akkor az érték kiszámítása
csak akkor kezdődik el, mikor ez az érték szükséges a végső eredmény kiszámításához. Például ha a
végtelen listának csak egy adott elemére van szükségünk, akkor a számítás nem fogja megkövetelni
az egész lista kiértékelését, csak annak azon részét, mely ennek az elemnek a kiszámításához szükséges.
Így az ilyen számításokat végre lehet hajtani véges időben még akkor is, ha végtelen listával dolgozunk.
Természetesen, ha az a feladat, hogy egy végtelen lista utolsó elemét találjuk meg vagy egy végtelen
listát állítsunk elő, akkor a számítás nem fog terminálni. Ez utóbbi esetben a generált végtelen
lista elemeinek értéke balról jobbra haladva kinyomtatódik, mihelyst valamely elem normál formába
kerül.A végtelen adatstrukturák definiálásának lehetősége nagyon elegáns programokat eredményezhet. Például ha egy olyan függvényt kell definiálnunk, mely megadja az első 1000 prímszámot, akkor ez egyszerűen megtehető úgy, hogy vesszük a prímek végtelen listájának első 1000 elemét.
A lusta ill. mohó kiértékelés közti különbség egy példán keresztül bemutatva, ahol a feladat második prímszám megadása:
Mohó kiértékeléssel:
hd (tl (sieve (gen 2)))
-> hd (tl (sieve (2 : gen (inc 2))))
-> hd (tl (sieve (2 : gen 3)))
-> hd (tl (sieve (2 : 3 : gen (inc 3))))
-> hd (tl (sieve (2 : 3 : ... )
Lusta kiértékeléssel:
hd (tl (sieve (gen 2)))
-> hd (tl (sieve (2 : gen (inc 2))))
-> hd (tl (2 : sieve (filter 2 (gen (inc 2)))))
-> hd (sieve (filter 2 (gen (inc 2))))
-> hd (sieve (filter 2 (inc 2 : gen (inc (inc 2)))))
-> hd (sieve (filter 2 (3 : gen (inc (inc 2)))))
-> hd (sieve (3 : filter 2 (gen (inc (inc 2)))))
-> hd (3 : sieve (filter (filter 2 (gen (inc (inc 2))))))
-> 3
Egy érdekes alkalmazása a végtelen listáknak, amikor egy függvény értékeinek ideiglenes tárolására alkalmazzuk. Például a korábban
megadott naív definíciója a fib Fibonacci-számokat előállító függvénynek a következőképpen módosítható, hogy hatékonysága exponenciálisról
lineárisra csökkenjen: fib 0 = 1
fib 1 = 1
fib (n+2) = flist!(n+1) + flist!n || a rekurziót módosítottuk, hogy kereső táblát (listát) használjon
where flist = map fib [0..]
További említésreméltó lehetősége a végtelen listáknak, hogy segítségükkel kommunikáló folyamatok hálózatát reprezentáló funkcionális programokat
írhatunk. Például a Hamming-számok problémája, mely esetén növekvő sorrendben kell meghatároznunk a 2^a*3^b*5^c (a,b,c<=0) számokat. Kommunikáló
folyamatokkal szép megoldását adhatjuk a feladatnak, amely Mirandában így néz ki: hamming = 1 : merge (f 2) (merge (f 3) (f 5))
where f a = [n*a | n <- hamming]
merge (a:x) (b:y) = a : merge x (b:y), if a=b
: merge (a:x) y, if a=a
: merge x y, otherwise