A Miranda programozási nyelv

Listák

Listák

A Miranda három alternatív jelölést biztosít a listák definiálására, mégpedig olyan formában, mely hasonlóan használatos a matematikában is: pont-pont kifejezés, ZF-kifejezés és rekurzív generálás. Elõnyük, hogy elegánsak, és jobban olvashatók. A hátrányuk, hogy kevésbé látható az, hogy a lista milyen módon lesz kiszámítva.

Pont-pont kifejezés

A következõ rövidítések olyan listák definiálására készültek, melyek elemeinek formája véges vagy végtelen aritmetikai sorozat. Legyen a, b, c tetszõleges numerikus kifejezés, ekkor:
 [a..b]: véges lista, mely a számokat tartalamazza a-tól 1-es távolságokkal, és az utolsó elem nem haladja meg b-t
 [a..]: végtelen lista a-tól, egyesével növekedve
 [a,b..c]: véges lista a-tól (b-a) hosszú lépésközökkel úgy, hogy az utolsó elem nem haladja meg c-t
A következõ példák mutatják, hogy hogyan lehet használni ezeket a rövidítéseket együtt. A következõ két segédfüggvényt a rövidítések kiterjesztésére használjuk:

inbetween:: num->num->num->[num]

inbetween start limit interval = start : inbetween (start + interval) limit interval, (interval >= 0 & start <= limit) \/ (interval <= 0 & start >= limit)
                               = [], otherwise

from:: num->num->[num]
from start interval = start : from (start + interval) interval

Példa a pont-pont definícióra:

ciphers:: [num]    || számjegyek
ciphers = [0..9]    vagy    ciphers = inbetween 0 9 1

nats:: [num]    || természetes számok
nats = [1..]    vagy    nats = from 1 1

evenciphers = [0,2..9]    vagy    evenciphers = inbetween 0 9 (2-0)    || páros számok

evens = [2,4..]    vagy    evens = from 2 (4-2)    || páros természetes számok

ZF-kifejezés

A ZF-kifejezések a listák feletti iterációk egy meglehetõsen általános osztályára adnak egy tömör szintaxist. A jelölést a Zermelo-Fraenkel teóriából adaptálták. Általában a ZF-kifejezéseknek két lehetséges formája van: [kifejezés | képzõ] vagy [kifejezés // képzõ]. Ez a kifejezés egy olyan listát eredményez, melynek elemei a kifejezés által meghatározott formájúak, és a képzõvel vannak elõállítva. Amikor összetett képzõt specifikálunk, akkor pontosvesszõvel kell elválasztani õket egymástól. Két fajta képzõ létezik: generátor és szûrõ.
Ha generátor, akkor a formája: minta1, minta2, ... mintan <- kifejezés, mely rövidített formája a következõ összetett generátornak: minta1<-kifejezés; minta2<-kifejezés; ... mintan<-kifejezés A példában a sq függvény eredményül a természetes számok négyzeteinek egy növekvõen rendezett végtelen listáját adja. Ez a ZF-kifejezés n*n-eket fogja sorban adni, ahogy n-t az [1..] végtelen lista sorban adja. Az n minta csak egy egyszerû a ZF-kifejezésre kiterjedõ lokális változó.

sq:: [num] sq = [n*n | n<-[1..]]

cubes:: [num] cubes = [x*y | (x,y)<-sqlist]

sqlist:: [(num,num)]
sqlist = [(n,n*n) | n<-[1..]]

Példa összetett generátorral:

list:: [(num,num)]
list = [(x,y) | x,y <-[1..2]]

amely a következõ rövidítése:

list = [(x,y) | x<-[1..2]; y <-[1..2]]

A legjobboldalibb generátor változik elsõnek, így az eredmény a következõ tuple-kból álló lista: [(1,1),(1,2),(2,1),(2,2)].
Ha a képzõ szûrõ, akkor egy megszorítást vetünk ki a generátor által létrehozott objektumokra. A factors függvény a kapott n szám összes tényezõjét adja meg, használva a szûrõ képzõt.

factor:: num->[num]
factor n = [r | r<-[1..n div 2]; n mod r = 0]

Jó demonstrációja a ZF-kifejezések eleganciájának a quicksortra adott következõ definíció.

quicksort:: [num]->[num]
quicksort [] = []
quicksort (a : x) = quicksort [b | b<-x; b<=a]
                    ++ [a] ++
                    quicksort [b | b<-x; b>a]

Mivelhogy az összetett generátoroknak mindig a jobboldali generátora fog elõször változni, a többi generátor nem tud új megoldást adni, ha a jobboldali egy végtelen sorozatot generál. A Pithagorasz-számok megadása végtelen lista feletti összetett generátorokkal:

pyths:: [(num,num,num)]

pyths = [(a,b,c) | a,b,c <-[1..]; a^2+b^2=c^2]

Nem fog eredményt adni, mert a generátor változása végtelen listát ad: [(1,1,1),(1,1,2),(1,1,3)...]. Az ilyen probblémákat, ha minden generátornak azonos a prioritása, akkor meg lehet oldani a generátorok diagonalizálásával. Ekkor szélességi balról-jobbra kiértékelést fog használni a mélységi helyett. Ez a különbség a generátorok specifikálásakor // jelet használva a | helyett.

pyths = [(a,b,c) // a,b,c <-[1..]; a^2+b^2=c^2]

A Pithagorasz-számok diagonizált generátor esetén adnak eredményt, a generátor változása: [(1,1,1),(1,2,1),(1,1,2),(2,1,1)...]

Rekurzív generálás

A rekurzív generátorok lehetõvé teszik listák konstruálását tetszõleges rekurzív relációk és a pont-pont jelölés használatával. Ennek a rekurzív generátornak a jelentése kifejezhetõ egy normál operátor kiterjesztésével, a következõ módon:

minta <- iterate f kifejezés1
where f minta = kifejezés2

iterate:: (*->*)->*->[*]
iterate f x = x : iterate f (f x)

Az iteráció eredménye egy végtelen lista: [x, f x, f (f x),...]
A rekurzív generátorok speciális szintaktikai konstrukciók egy speciális rekurzív definiálásra, a lista generálásra.

Jól szemlélteti a tömörséget a 8-kiralynõ probléma Miranda megoldása is. Tehát el kell helyeznünk 8 kiralynõt egy sakktáblán, hogy egyikük se álljon sakkban akármelyik másikkal. Miután mindegyik megoldásban egy oszlopban egy és csak egy királynõ áll, ezért a megfelelõ reprezentációja a táblának egy integer lista, mely sorrendben mindegyik oszlophoz megadja hogy annak mely sorában áll a királynõje. A következõ queens n függvény megadja az összes biztonságos királynõ elhelyezést az elsõ n oszlopra. Tehát a 8-királynõ probléma összes megoldásának listája a queens 8 kiértékelésével kapható meg:

queens 0 = [[]]
queens (n+1) = [q:b | b <- queens n; q <- [0..7];
safe q b] safe q b = and [ ~checks q b i | i <- [0..#b-1]]
checks q b i = q=b!i \/ abs(q - b!i)=i+1