Nimistute töötlemine

Järgnevas vaatleme mõningaid sageli esinevaid nimistute töötlemise ülesandeid. Mmitmed neist on süsteemipredikaatidena juba olemas, kuid nende kasutamisel tekib sageli probleeme, mida ilma vastava mooduli teksti uurimata või vastavat predikaati mitmel viisil katsetamiseta väga raske lahendada - kas member võimaldab ka nimistu elemente genereerida, kas nimistust elementi eemaldades eemaldatakse kõik selle esinemised või ainult esimene/viimane jnejne. "Oma" (ise kirjutatud) predikaatide korral on palju kergem aru saada, kuidas predikaat töötab.

Nimistu pikkuse leidmine - tühja nimistu pikkus on 0 ja pikema nimistu pikkus on keha pikkusest ühe võrra suurem:

pikkus([],0):-!. %edasi pole enam vaja uurida!
pikkus([_|Keha],N):-
pikkus(Keha,N1),
N is N1 + 1.

Predikaat (sageli süsteemipredikaat) append(Nimistu1, Nimistu2, Nimistu) yhendab nimistud Nimistu1 ja Nimistu2 üheks nimistuks Nimistu:

append([],L,L):-!.
append([Element|Keha],Nimistu,[Element|Keha1]):-
append(Keha,Nimistu,Keha1).

Arvnimistu elementide summa:

summa([],0):-!.
% Tühja nimistu elementide summa on 0
summa([Esimene|Muud], S)):-
summa(Muud, S1),
S is S1 + Esimene.

Arvnimistu elementide aritmeetiline keskmine:

keskmine(Nimistu, Keskmine):-
pikkus(Nimistu, P),
summa(Nimistu, S),
Keskmine is S/P.

Arvnimistu (mittetühja) elementide seast suurima leidmisel on võib kasutada Prologi süsteemifunktsiooni max(X, Y):

suurim([X], X):-!.
% Üheelemendilise nimistu suurim element on see ainuke element
suurim([Esimene| Muud], Max):-
suurim(Muud, Max1),
Max is max(Max1, Esimene).

Nimistu minimaalse (või maksimaalse) elemendi võib leida ka ilma süsteemifunktsiooni kasutamata:

min([X], X):-!.
% üheelemendilise nimistu ainuke element ongi minimaalne!
min([Esimene|Muud], Esimene)):-
min(Muud, Min1),
Esimene < Min1,
!. %kui Esimene on väiksem kui Muud-e miinimum, siis Esimene ongi miinimum
min([_|Muud], Min)):-
min(Muud, Min),
%kui seda lauset peab kasutama,
%ei ole esimene element minimaalne,
%seega tema väärtus pole enam oluline!

Tingimust Tingimus täitvate elementide Term (Term võib olla muutuja, lõplik nimistu jne) kogumiseks nimistuks Nimistu on olemas süsteemipredikaat findall(Term, Tingimus, Nimistu). Kui pojad on kirjeldatud lausetega poeg_on(Isa, Poeg), siis Isa-e poegade arvu võib arvutada järgmiselt:

poegi(Isa, Mitu):-
findall(Poeg, poeg_on(Isa, Poeg), Pojad),
pikkus(Pojad, Mitu).
Eelnev võib anda vale tulemuse, kui mõni poeg on kirjeldatud kaks korda (kaks ühesugust lauset poeg_on(Isa, Poeg)), sest findall ei eemalda loodud nimistust korduvaid elemente. Alati õige tulemuse saame, kui eelnevas findall asemel kasutada Prologi süsteemipredikaati setof - see eemaldab korduvad ja järjestab nimistu elemendid.
Ülesandeid:
1. Koosta predikaat reverse(Nimistu,Pööratud), mis muudab nimistu Nimistu elementide järjekorra vastupidiseks; predikaat peab töötama nii siis, kui antud on nimistu Nimistu, kui ka siis kui antud on nimistu Pööratud või kui mõlemad on antud.
2. Koosta predikaat flatten(Nimistu1, Nimistu2), mis "tasandab" nimistu Nimistu1, s.t. muudab kõik selle alamnimistud uue nimistu Nimistu2 elementideks; predikaat peab olema rekursiivne, s.t. peab toimima samal viisil ka alam-alam-nimistutega jne, näiteks peab kehtima flatten([a,[[a1,a2],a3]],[a,a1,a2,a3]).
3. Koosta predikaadid:
remove(Element, Nimistu1, Nimistu2) - eemaldab elemendi Element (kõik esinemised) nimistust Nimistu1;
remove(N, Nimistu1, Nimistu2) - eemaldab nimistust Nimistu1 N-da elemendi (N <= nimistu Nimistu1 pikkus);
add(Element,N,Nimistu1, Nimistu2) - lisab nimistu Nimistu1 N-daks elemendiks elemendi Element.
4.

Koosta predikaat meililisti osavõtjatele signatuuride moodustamiseks. Signatuur (aatom) moodustatakse osavõtja nimest (aatom), kasutades sümboleid nimistust [' ', '.', '/', '<', '>', '?', '!', ':', '\', '|', '{', '}', '-', '=', '_', '+', '@', '#', '$', '%', '^', '&', '*', '(', ')', '~','`'] (fikseeritud) ja kolme operaatorit; kõigi operaatorite argumentideks on nimi ja mingi eespoolloetletud sümbolitest koostatud aatom; operaatorid on :
prefiks - lisab sümbolite aatomi nime ette;
suffiks - lisab sümbolite aatomi nime lõppu (samas järjekorras);
ymber - lisab sümbolite aatomi nime ette ja (tagurpidi järjekorras) nime lõppu.
Operaatorid antakse nimistuna, mille iga element on kahekohaline nimistu [operaator, sümbolid] ja nad tuleb sooritada selles järjekorras nagu nad on nimistus esitatud; näiteks kui nimi on 'Juku' ja operaatorite nimistu [[[ymber,'-='], [suffiks, '-( ('], [prefiks,'(-']] , siis tulemuseks tuleb (samm sammult) 'Juku' '-=Juku=-' '-=Juku=--( (' '(--=Juku=-) )'. Koosta predikaat signatuur(Nimi, Operaatorid,Signatuur), mis moodustab signatuuri Signatuur . Operaatorite nimistu võib olla kuitahes pikk (võib ka tühi olla), kuid predikaat peaks lõpetama töö, kui signatuuri pikkus tuleks järgneval sammul suurem kui 20; predikaat peaks ka kontrollima, et operaatorite argumendid on koostatud ainult lubatud (ülalesitatud nimistu) sümbolitest.


Küsimused, probleemid: ©2004 Jaak Henno