From a9416de1d2bde1b2327928717d00d262160912af Mon Sep 17 00:00:00 2001
From: Timotej Lazar
-Seznami so verjetno daleč najbolj pomembna podatkovna struktura v prologu.
+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 veliko uporabljali, saj s seznami lahko naredimo res marsikaj.
+bomo pogosto uporabljali, saj s seznami lahko naredimo res marsikaj.
Kot vidiš, je zapis preprost in očiten. Med oglate oklepaje enostavno naštejemo
-elemente seznama, ki jih med seboj ločimo z vejico.
+elemente seznama, ki jih med seboj ločimo z vejicami.
-Naslednje vprašanje. Kaj so lahko elementi seznama, morajo morda biti istega
+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:
@@ -165,19 +165,19 @@ seznam? Zakaj?
Tako je. Spomnimo se, da je prolog logični jezik. Če bi napisal
-Zato je potrebno uvesti novo spremenljivko, ki naredi nov seznam (zgoraj je to
-
-Najbolje, da eno nalogo sprogramiramo skupaj. Naloga naj bo naslednja: predikat
+Najbolje, da eno nalogo sprogramiramo skupaj. Naloga je naslednja: predikat
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.
+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.
@@ -232,11 +232,11 @@ insert(X, L, L1) :- % procent je oznaka za vrstični komentar v prologu
-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.
+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.
Prolog: seznami
Kako izgledajo seznami v prologu?
@@ -26,11 +26,11 @@ Torej, kako sezname v prologu zapišemo, predstavimo? Tole je primer seznama:
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.
+(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
+aritmetiko: spremenljivki, ki ima vrednost 3, ne moreš kar prišteti ena, ker 3
logično ni enako 4.
L1
). Pa ni to pomnilniško potratno. Je, vendar za to skrbi
+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.
Kako programiramo s seznami?
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:
+element, vstavljen na vsa možna mesta. Primer:
?- insert(a, [1,2,3], L1).
@@ -218,9 +218,9 @@ false.
insert(X, L, L1) :-
@@ -251,7 +251,7 @@ 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
+predpostavko prej), potem je L1
enak seznamu L
z
vstavljenim elementom X
. Logično! 😊
@@ -290,13 +290,13 @@ insert(X, [H|T], [H|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 predikatinsert/3
s klicem -insert(a, [1,2,3], L1)
in se aktivira njegov rekurzivni stavek -(drugi), se ob klicu zgodi naslednja prilagoditev: +=
(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 predikatinsert/3
+s kliceminsert(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]) @@ -317,9 +317,9 @@ 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. +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.