[a,b,c]Seznami so verjetno daleč najbolj pomembna 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 veliko 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 vejico.
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 unifikacijo). 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 naredi 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 naj bo 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 vse različne načine. 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 mi je nekako namig glede strategije: 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, prav kot smo to počeli prej. Sedaj pa poglejmo kako bi vstavil v rep. 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 (v rep vstavljen element), 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 seznam 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 seznamo, 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
= (unifikacija) 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 (unifikacija) na način kot so zapisani argumenti v glavi
stavka. 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, naloga morda deluje tudi v kakšno nepričakovano „smer“. In tole bi morebiti znalo priti prav tudi pri kakšni kombinatorični nalogi kasneje.