1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
|
<!DOCTYPE html>
<html lang="sl">
<head>
<meta charset="utf-8" />
<title>Prolog: seznami</title>
<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
<link rel="stylesheet" type="text/css" href="../../style.css" />
</head>
<body>
<h1>Prolog: seznami</h1>
<p>
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.
</p>
<h2>Kako izgledajo seznami v prologu?</h2>
<p>
Torej, kako sezname v prologu zapišemo, predstavimo? Tole je primer seznama:
</p>
<pre>
?- L = [a,b,c].
</pre>
<p>
Kot vidiš, je zapis preprost in očiten. Med oglate oklepaje enostavno naštejemo
elemente seznama, ki jih med seboj ločimo z vejicami.
</p>
<p>
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:
</p>
<pre>
?- L = [a, 3, 3.14, [], [a,b,c], sin(a), parent(tina,william)].
</pre>
<p>
V ta seznam sem torej stlačil atom (konstanto) <code>a</code>, število
<code>3</code>, število v plavajoči vejici <code>3.14</code>, prazen seznam
<code>[]</code>, seznam <code>[a,b,c]</code>, strukturo <code>sin(a)</code> in
strukturo (tako je, to ni predikat!) <code>parent(tina, william)</code>. 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:
</p>
<pre>
?- L = [a,b,c,X,Y,Z].
</pre>
<p>
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.
</p>
<p>
Dobro, kako pa do posameznih elementov dostopam, ko jih potrebujem? Jih lahko
naslavljam po indeksu (mestu v seznamu)? Lahko pišem <code>L[3]</code>? 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 (<code>.</code>), 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 <code>[]</code>.
</p>
<p>
Seznam <code>[a,b,c]</code> je interno v resnici
<code>.(a, .(b, .(c, [])))</code>; tako ga lahko tudi zapišeš (opomba: novejše
verzije SWI-Prologa in tudi <span class="codeq">CodeQ</span> namesto
<code>.</code> uporabljajo <code>[|]</code>).
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.
</p>
<figure>
<img src="list.svg" />
<figcaption>Struktura seznama <code>[a,b,c]</code></figcaption>
</figure>
<p>
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.
</p>
<p>
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.
</p>
<pre>
?- L = [a,b,c], L = [Head|Tail].
</pre>
<p>
Kaj smo zapisali? V prvem delu konjunkcije (pred vejico) smo spremenljivki
<code>L</code> „priredili“ seznam <code>[a,b,c]</code>, v drugem delu pa smo
seznam „razbili“ na dva dela z navpičnico: na prvi element in na preostanek,
oboje pa shranili v spremenljivki <code>Head</code> in <code>Tail</code>.
Tako je, prvemu elementu seznama bomo rekli glava (<code>Head</code>),
preostanku seznama pa rep (<code>Tail</code>).
Spremenljivkama seveda lahko damo poljubno ime, velikokrat pa bomo uporabljali
kar <code>H</code> in <code>T</code>. Če prologu zgornje vprašanje zastavimo,
dobimo pričakovan odgovor:
</p>
<pre>
?- L = [a,b,c], L = [Head|Tail].
Head = a, Tail = [b,c].
</pre>
<p>
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:
</p>
<pre>
?- L = [a,b,c], L = [H1,H2|T].
H1 = a, H2 = b, T = [c].
</pre>
<p>
Zelo pomembno: glava seznama je <em>element</em> seznama in je lahko
<em>poljubnega tipa</em> (saj si videl, da so elementi seznama lahko karkoli),
medtem ko je rep seznama <em>vedno</em> seznam, pa četudi prazen! To bo v tem
sklopu verjetno ena najbolj pogostih napak, dokler se ne navadiš.
</p>
<p>
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:
</p>
<pre>
?- NewElement = d, L = [a,b,c], L1 = [NewElement|L].
L1 = [d,a,b,c].
</pre>
<p>
Aha, sedaj sem element vstavil! Tako je, na zapis <code>[H|T]</code> glej kot
na primerjanje vzorcev (<em>pattern matching</em>). Ali tudi na ostale zapise
seznamov, npr. <code>[H]</code> in <code>[X,Y,Z]</code>, ki ne pomenita drugega
kot seznam z enim oz. tremi elementi. Tako je, seznam z enim elementom je
preprosto <code>[H]</code>, ne potrebuješ pisati <code>[H|[]]</code> – to je
grdo (a seveda tudi deluje in pomeni enako).
</p>
<p>
Če si opazil, sem zgoraj uporabil novo spremenljivko <code>L1</code> ob
dodajanju elementa v seznam <code>L</code>. Zakaj? Sem s tem naredil nov
seznam? Zakaj?
</p>
<p>
Tako je. Spomnimo se, da je prolog logični jezik. Če bi napisal
<code>L = [NewElement|L]</code>, 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 <code>=</code> pomeni prilagajanje oz.
<em>unification</em>). Torej nek <code>L</code> 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 <code>L</code>) 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.
</p>
<p>
Zato je potrebno uvesti novo spremenljivko, ki predstavlja nov seznam (zgoraj
je to <code>L1</code>). Pa ni to pomnilniško potratno? Je, vendar za to skrbi
prologov <em>garbage collector</em>.
</p>
<p>
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.
</p>
<p>Kratek pregled pomembnih reči:</p>
<ul>
<li>v seznamih je lahko karkoli;</li>
<li>dostopaš vedno do glave seznama (ali več glav), do repa se moraš
(rekurzivno) prebiti;</li>
<li>na zapis <code>[H|T]</code> glej kot na primerjanje vzorcev;</li>
<li>ne razmišljaj o porabi pomnilnika, za to skrbi garbage collection;</li>
<li>glava seznama je poljubnega tipa, medtem, ko je rep seznama vedno seznam.</li>
</ul>
<h2>Kako programiramo s seznami?</h2>
<p>
Najbolje, da eno nalogo sprogramiramo skupaj. Naloga je naslednja: predikat
<code>insert/3</code> naj vstavi element <code>X</code> na poljubno mesto v
seznam <code>L</code> in vrne nov seznam <code>L1</code> 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:
</p>
<pre>
?- 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.
</pre>
<p>
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.
</p>
<p>
Vstavljanje na začetek je preprosto in to bo kar moj robni primer:
</p>
<pre>
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
</pre>
<p>
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.
</p>
<pre>
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
</pre>
<p>
Logično zgornje pravilo preberem takole: če je <code>L</code> sestavljen iz
glave <code>H</code> in repa <code>T</code> in hkrati predpostavim, da je
<code>NT</code> seznam <code>T</code> (rep) z vstavljenim elementom
<code>X</code> (kamorkoli) in je hkrati <code>L1</code> sestavljen iz glave
<code>H</code> ter repa <code>NT</code> (ki vsebuje <code>X</code>, glej
predpostavko prej), potem je <code>L1</code> enak seznamu <code>L</code> z
vstavljenim elementom <code>X</code>. Logično! 😊
</p>
<p>
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:
</p>
<pre>
?- L = [], L = [H|T].
false.
</pre>
<p>
Seveda, rekli smo, da je <code>L</code> 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“.
</p>
<p>
Zgornji program sem za lažje razumevanje napisal na zelo dolg (in grd) način.
Od zdaj bomo programirali takole:
</p>
<pre>
insert(X, L, [X|L]).
insert(X, [H|T], [H|NT]):-
insert(X, T, NT).
</pre>
<p>
Pomen je enak kot prej, le zapis je veliko krajši. Vse operatorje
<code>=</code> (prilagajanje oz. <em>unification</em>) 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 <code>insert/3</code>
s klicem <code>insert(a, [1,2,3], L1)</code> in se aktivira njegov rekurzivni
stavek (drugi), se ob klicu zgodi naslednja prilagoditev:
</p>
<pre>
insert(a, [1,2,3], L1) = insert(X, [H|T], [H|NT])
</pre>
<p>
kar pomeni:
</p>
<pre>
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]).
</pre>
<p>
Tako je, <code>NT</code> 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.
</p>
<p>
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.
</p>
</body>
</html>
|
