Listojen käsittelyä

Listat ovat Prologin perustietorakenne. Niille on paljon valmiita järjestelmäpredikaatteja, mutta siitä huolimatta usein joutuu tekemään itsekin rekursiivisia listaa käsitteleviä funktioita. Imperatiivisiin ohjelmointikieliin tottuneet saattavat kokea tämän hankalaksi, erityisesti kun sijoitusoperaatiota ei ole. Sen vuoksi käydään läpi muutamia esimerkkejä aiheesta.

Evens

Tehdään predikaatti evens(L1,L2), joka karsii saamastaan listasta L1 parittomat alkiot pois.

 % tyhjälle listalle evens-lista on tyhjä
lista evens([],[]).

% jos listan ensimmäinen alkio on parillinen lisätään 
% se myös parillisten listaan
evens([X|L1],[X|L2]) :- 
    0 is X mod 2,
    !,
    evens(L1,L2).

% muuten siirrytään käsittelemään seuraavaa alkiota
evens([X|L1],L2) :-
    evens(L1,L2).

Kokeillaan predikaattia siten, että L2 on muuttuja, ja L1 on tunnettu. Predikaatti näyttäisi toimivan ihan oikein. Testataan sitä siten, että molemman parametrit ovat tunnettuja, vaikkapa evens([1,2,3,4],[2]). Yllättäen vastaus onkin true. Mistä tämä johtuu? No tietenkin siitä, että kun L2, on tyhjä lista, ei suoritus ikinä pääse keskimmäisen kaavan leikkaukseen asti, minkä vuoksi se voi esteittä mennä viimeiseen kaavaan kerta toisensa jälkeen, kunnes molemmat listat ovat tyhjiä ja kohdataan rekursion pohja.

Miten tämä virhe korjataan (jos päätämme pitää sitä virheenä)? Helposti, lisätään vaan ylimääräinen tarkastus viimeiseen kaavaan. Tällöin leikkaus ei ole enää välttämätön, vaan se muuttuu vihreäksi leikkaukseksi, joka vain hieman tehostaa ohjelman toimintaa, eikä synnytä järjestysriippuvuutta. Virheiden välttämiseksi kannattaa suosia vihreitä leikkauksia.

% muuten siirrytään käsittelemään seuraavaa alkiota
evens([X|L1],L2) :-
    1 is X mod 2,
    evens(L1,L2).

Listan käsittelyalgoritmit kannattaa pohtia aika tarkkaan ja erityisesti kannattaa miettiä, mitkä parametreista saavat olla tuntemattomia ja mitkä tunnettuja. Mikäli huomaatte, että kirjoittamanne predikaatti toimii yllättävällä tavalla jossakin tilanteessa, kirjatkaa se ylös.

Järjestettyjen listojen limitys

Tehdään vähän monimutkaisempi esimerkki, predikaatti limita(L1,L2,L), joka yhdistää järjestetyt listat L1 ja L2 siten, että tuloslista L on myös järjestetty. Eli listat käydään läpi siten, että otetaan aina listojen L1 ja L2 alkioista pienempi ja liitetään se listan L ensimmäiseksi alkioksi. Näin ensimmäisellä rekursion tasolla listan L ensimmäiseksi alkioksi asetetaan kaikista pienin alkio (esiehtona tietenkin on, että listat L1 ja L2 ovat suuruusjärjestyksessä) ja seuraavalla tasolla seuraavaksi pienin alkio jne.

limita([],[],[]).

limita([X1|L1],[],[X1|L]) :-
    !,
    limita(L1,[],L).

limita([],[X2|L2],[X2|L]) :-
    !,
    limita([],L2,L).

limita([X1|L1],[X2|L2],[X1|L]) :-
    X1 < X2,
    !,
    limita(L1,[X2|L2],L).

limita([X1|L1],[X2|L2],[X2|L]) :-
    X2 =< X1,
    limita([X1|L1],L2,L).

Listan n-jaollisten alkioiden yhteenlasku

Otetaan vielä hieman erityyppinen listatehtävä, jossa listoja ei muokata, vaan niiden avulla lasketaan jotakin. Predikaatti onnistuu S on listan käsittelyn alla olevan osan n:llä jaollisten lukujen summa.
n_jaollisten_summa([],N,0).
    
n_jaollisten_summa([X|L],N,S) :-
    0 is X mod N,
    !,
    n_jaollisten_summa(L,N,S2),
    S is S2 + X.

n_jaollisten_summa([_X|L],N,S) :-
    n_jaollisten_summa(L,N,S).

Tämä ei ole kuitenkaan tehokkain tapa, koska keskimmäisessä kaavassa rekursiivisen predikaatin jälkeen tehdään vielä muutakin, eikä se siis ole häntärekursiivinen. Tehokkuuden vuoksi kannattaisi suosia häntärekursiota, koska Prologtulkki pystyy usein suorittamaan sen tehokkaammin kuin muunlaisen rekursion. Muokattaessa predikaatti häntärekursiiviseksi otetaan käyttöön ylimääräinen muuttuja, ns. akkumulaattori (accumulator), johon välitulokset talletetaan käytäessä listaa läpi. Huomaa, että jokaisella rekursion tasolla akkumulaattorista A on olemassa eri versio, joka sidotaan arvoon, jolla predikaatin esittämä ehto toteutuu, mutta lopullinen summa S pysyy sitomattomana kunnes saavutetaan rekursion pohja eli tyhjä lista.

 
n_jaollisten_summa(L,N,S) :- n_jaollisten_summa(L,N,S,0).

n_jaollisten_summa([],N,S,S).
    
n_jaollisten_summa([X|L],N,S,A) :-
    0 is X mod N,
    !,
    A2 is A+X,
    n_jaollisten_summa(L,N,S,A2).

n_jaollisten_summa([_X|L],N,S,A) :-
    n_jaollisten_summa(L,N,S,A).