[a,b,c]Seznami so daleč najpomembnejša podatkovna struktura v prologu. Poleg tega so tudi zelo primerni za začetni, pa vseeno precej resen, skok v svet rekurzije, kar bomo z veseljem izkoristili! Vendar pa operacije na seznamih, ki jih boš implementiral danes, niso tu samo za vajo. Kasneje jih bomo pogosto uporabljali, saj s seznami lahko naredimo res marsikaj.
Torej, kako sezname v prologu zapišemo, predstavimo? Tole je primer seznama:
?- L = [a,b,c].
Kot vidiš, je zapis preprost in očiten. Med oglate oklepaje enostavno naštejemo elemente seznama, ki jih med seboj ločimo z vejicami.
Naslednje vprašanje: kaj so lahko elementi seznama, morajo morda biti istega tipa? Hmm, tipi v prologu, s tem se ne bomo ukvarjali danes, ampak v enem izmed kasnejših poglavij. Da ne zavlačujem: v prologovih seznamih lahko skupaj shranjuješ karkoli. Karkoli. Skratka, tole je povsem legalno:
?- L = [a, 3, 3.14, [], [a,b,c], sin(a), parent(tina,william)].
V ta seznam sem torej stlačil atom (konstanto) a, število
3, število v plavajoči vejici 3.14, prazen seznam
[], seznam [a,b,c], strukturo sin(a) in
strukturo (tako je, to ni predikat!) parent(tina, william). Saj
sem rekel, da je v seznamu lahko karkoli. Nič posebnega, boš dejal, to lahko
tudi v kakšnem drugem jeziku, npr. v pythonu. Drži, drži, kaj pa tole:
?- L = [a,b,c,X,Y,Z].
Samo malo, kaj nismo z veliko začetnico označevali spremenljivk? Smo. Kako pa prolog ve, kakšne vrednosti imajo? Ne ve. In so vseeno lahko v seznamu, ne da bi poznali njihove vrednosti? Tako je! In ko morda kasneje dobijo neko vrednost? Bo ta v seznamu.
Dobro, kako pa do posameznih elementov dostopam, ko jih potrebujem? Jih lahko
naslavljam po indeksu (mestu v seznamu)? Lahko pišem L[3]? Ne. Ne,
res ne? Res ne. Poglejmo še malo, kako so seznami predstavljeni interno, in boš
razumel, zakaj ne. Vse reči v prologu so interno predstavljene z drevesi in to
velja tudi za sezname. Seznam je v resnici struktura (to se boš učil kasneje),
katere ime je simbol pika (.), sprejme pa dva argumenta: prvi
element seznama in seznam(!) preostalih elementov. Tako je, seznam je definiran
rekurzivno! Prazen seznam je posebnost in mu pripada simbol [].
Seznam [a,b,c] je interno v resnici
.(a, .(b, .(c, []))); tako ga lahko tudi zapišeš (opomba: novejše
verzije SWI-Prologa in tudi CodeQ namesto
. uporabljajo [|]).
Za ljudi je ta zapis precej štorast, zato obstaja alternativni zapis z oglatimi
oklepaji, ki smo ga spoznali na začetku. A v resnici je ta zapis samo
sintaktični sladkorček in se interno prevede v zapis s piko, prikazan na
spodnji sliki.
[a,b,c]Skratka, seznam je v resnici izrojeno drevo, po katerem se moramo sprehoditi do iskanega elementa. Lahko si ga predstavljamo kot vrsto ljudi: dostop imamo le do prvega človeka v vrsti, do ostalih pa pridemo tako, da prvega „obdelamo“ in ga vzamemo iz vrste. In tako naprej, dokler ne najdemo iskanega elementa ali dokler ni seznam prazen. Nekoliko štorasto morda, a zdaj razumeš, zakaj je tako.
Prolog ima vgrajen še en sintaktični sladkorček za lažji zapis takšnega dostopa do elementov seznama. To je zapis z navpičnico, ki ga bomo neprestano uporabljali.
?- L = [a,b,c], L = [Head|Tail].
Kaj smo zapisali? V prvem delu konjunkcije (pred vejico) smo spremenljivki
L „priredili“ seznam [a,b,c], v drugem delu pa smo
seznam „razbili“ na dva dela z navpičnico: na prvi element in na preostanek,
oboje pa shranili v spremenljivki Head in Tail.
Tako je, prvemu elementu seznama bomo rekli glava (Head),
preostanku seznama pa rep (Tail).
Spremenljivkama seveda lahko damo poljubno ime, velikokrat pa bomo uporabljali
kar H in T. Če prologu zgornje vprašanje zastavimo,
dobimo pričakovan odgovor:
?- L = [a,b,c], L = [Head|Tail]. Head = a, Tail = [b,c].
Kot vidiš, imaš enostaven dostop do prvega elementa in do preostanka seznama. Pravzaprav celo nekoliko več, na začetku namreč lahko pišeš poljubno število glav, ločenih z vejico. Poskusi tole:
?- L = [a,b,c], L = [H1,H2|T]. H1 = a, H2 = b, T = [c].
Zelo pomembno: glava seznama je element seznama in je lahko poljubnega tipa (saj si videl, da so elementi seznama lahko karkoli), medtem ko je rep seznama vedno seznam, pa četudi prazen! To bo v tem sklopu verjetno ena najbolj pogostih napak, dokler se ne navadiš.
Prejle sem rekel, da z navpičnico seznam razbijemo. Ampak kot se spomniš, v prologu reči večinoma delujejo v vse mogoče smeri. In razbijanje je ravno nasprotno od sestavljanja. Primer:
?- NewElement = d, L = [a,b,c], L1 = [NewElement|L]. L1 = [d,a,b,c].
Aha, sedaj sem element vstavil! Tako je, na zapis [H|T] glej kot
na primerjanje vzorcev (pattern matching). Ali tudi na ostale zapise
seznamov, npr. [H] in [X,Y,Z], ki ne pomenita drugega
kot seznam z enim oz. tremi elementi. Tako je, seznam z enim elementom je
preprosto [H], ne potrebuješ pisati [H|[]] – to je
grdo (a seveda tudi deluje in pomeni enako).
Če si opazil, sem zgoraj uporabil novo spremenljivko L1 ob
dodajanju elementa v seznam L. Zakaj? Sem s tem naredil nov
seznam? Zakaj?
Tako je. Spomnimo se, da je prolog logični jezik. Če bi napisal
L = [NewElement|L], kaj bi s tem logično povedal? Prolog bi
vprašal oz. mu naročil, da lahko naredi levo in desno stran enačaja enako
(spomni se, operator = pomeni prilagajanje oz.
unification). Torej nek L bi moral postati enak samemu
sebi s tem, da bi imel na začetku še en element.
Ali seznam s tremi elementi (recimo, da so trije v L) bi moral
postati enak seznamu s štirimi elementi. Mislim, da prologov odgovor poznaš.
„No!“ (In to zelo glasen ne.) Na to se spomni kasneje, ko bomo imeli opravka z
aritmetiko: spremenljivki, ki ima vrednost 3, ne moreš kar prišteti ena, ker 3
logično ni enako 4.
Zato je potrebno uvesti novo spremenljivko, ki predstavlja nov seznam (zgoraj
je to L1). Pa ni to pomnilniško potratno? Je, vendar za to skrbi
prologov garbage collector.
Zanimivost: prolog je bil eden izmed prvih jezikov (tam v sedemdesetih letih), ki je imel samodejni garbage collector. Takrat je bil pomnilnik izredno dragocena reč in je bilo praktično bogokletno pomisliti na to, da bi za nadzor nad porabo skrbel računalnik sam, to je bilo prepuščeno programerju. A pri prologu seveda ni šlo drugače, preprosto zaradi zasnove jezika.
Kratek pregled pomembnih reči:
[H|T] glej kot na primerjanje vzorcev;
Najbolje, da eno nalogo sprogramiramo skupaj. Naloga je naslednja: predikat
insert/3 naj vstavi element X na poljubno mesto v
seznam L in vrne nov seznam L1 z vstavljenim
elementom. Eno za drugo (z vračanjem) naj vrne vse možne rešitve – torej
element, vstavljen na vsa možna mesta. Primer:
?- insert(a, [1,2,3], L1). L1 = [a,1,2,3] ; L1 = [1,a,2,3] ; L1 = [1,2,a,3] ; L1 = [1,2,3,a] ; false.
Prav, kako začeti? Dostop imam le do začetka seznama, do ostalih mest se moram prebiti. To nakazuje strategijo, ki jo moram ubrati: ali vstavim takoj (na trenutni začetek), ali pa vstavim nekam v rep. In rekurzivno vse skupaj ponovim – oziroma ponovi kar prolog sam.
Vstavljanje na začetek je preprosto in to bo kar moj robni primer:
insert(X, L, L1) :- % procent je oznaka za vrstični komentar v prologu
L1 = [X|L]. % L1 izgleda kot vzorec: X na prvem mestu, rep je pa cel seznam L
Izkoristil sem navpičnico za sestavljanje večjega seznama, tako kot smo to počeli prej. Sedaj pa poglejmo, kako vstaviti element v rep seznama. Hja, prvi element bom dal (začasno!) stran, vstavil v rep (pustil rekurziji, da se sama odloči, kam) in, ko od rekurzije dobim odgovor (rep z vstavljenim elementom), dokončam rešitev tako, da dam prvi element nazaj na svoje mesto.
insert(X, L, L1) :-
L = [H|T], % L „razbijem“ na glavo in rep
insert(X, T, NT), % vstavi X nekam v rep (rekurzija)
L1 = [H|NT]. % predpostavim, da je rekurzija vstavila X v rep in sestavim končno rešitev
Logično zgornje pravilo preberem takole: če je L sestavljen iz
glave H in repa T in hkrati predpostavim, da je
NT seznam T (rep) z vstavljenim elementom
X (kamorkoli) in je hkrati L1 sestavljen iz glave
H ter repa NT (ki vsebuje X, glej
predpostavko prej), potem je L1 enak seznamu L z
vstavljenim elementom X. Logično! 😊
Kaj mi je omogočilo uporabo rekurzije? Problem vstavljanja mora z vsako uporabo rekurzije obvezno biti manjši. In kaj je „manjši“ z vidika seznamov? Seveda, krajši seznam! In rep je vedno vsaj za en element krajši od celotnega seznama – za glavo (ali več njih) krajši! In še drugi pogoj: rekurzija se mora nekoč ustaviti. Tudi to drži: prej sem napisal robni pogoj, ko se element enkrat vstavi, bo rekurzije konec. Kdaj se bo to zgodilo, se odloči prolog sam – z vsako zahtevo po novi rešitvi bo malce drugače, dokler se vse rešitve ne izčrpajo. Takrat bo prolog v bistvu toliko časa trgal glave stran, da bo ostal s praznim seznamom, ko ne bo več mogel ničesar odtrgati. Poskusi tole in boš razumel:
?- L = [], L = [H|T]. false.
Seveda, rekli smo, da je L prazen seznam in hkrati ga hotel
razbiti na glavo in rep. A glava mora biti element, tega pa nimamo. Zato
razstavljanje ne uspe in prolog reče „ne“.
Zgornji program sem za lažje razumevanje napisal na zelo dolg (in grd) način. Od zdaj bomo programirali takole:
insert(X, L, [X|L]).
insert(X, [H|T], [H|NT]):-
insert(X, T, NT).
Pomen je enak kot prej, le zapis je veliko krajši. Vse operatorje
= (prilagajanje oz. unification) sem zamenjal z
implicitno uporabo kar v argumentih predikata – temu pogovorno rečem kar
programiranje v glavi stavka. Spomnite se, da gre za primerjanje vzorcev. Tako
je, argumenti, ki jih predikat ob klicu dobi, se prilagodijo argumentom, kot so
zapisani v glavi pravila. Na primer: če pokličem predikat insert/3
s klicem insert(a, [1,2,3], L1) in se aktivira njegov rekurzivni
stavek (drugi), se ob klicu zgodi naslednja prilagoditev:
insert(a, [1,2,3], L1) = insert(X, [H|T], [H|NT])
kar pomeni:
X = a, [H|T] = [1,2,3] (kar dalje pomeni: H = 1 in T = [2,3]), [H|NT] = L1 (oz. dalje, ker vemo, da je H = 1: L1 = [1|NT]).
Tako je, NT ostane za zdaj spremenljivka brez določene vrednosti.
Saj se spomniš, da je to dovoljeno? No, tukaj bo prišlo prav, ker bo to kasneje
verjetno izračunala rekurzija.
Za konec: kakšen smisel ima vstavljanje na vsa možna mesta? Boš videl – predikat morda deluje tudi v kakšno nepričakovano „smer“. In to bi morebiti znalo priti prav tudi pri kakšni kombinatorični nalogi kasneje.