diff options
Diffstat (limited to 'prolog')
-rw-r--r-- | prolog/problems/lists/intro_sl.html | 66 |
1 files changed, 33 insertions, 33 deletions
diff --git a/prolog/problems/lists/intro_sl.html b/prolog/problems/lists/intro_sl.html index 2b59f5b..cd3f1a8 100644 --- a/prolog/problems/lists/intro_sl.html +++ b/prolog/problems/lists/intro_sl.html @@ -9,11 +9,11 @@ <h1>Prolog: seznami</h1> <p> -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. </p> <h2>Kako izgledajo seznami v prologu?</h2> @@ -26,11 +26,11 @@ Torej, kako sezname v prologu zapišemo, predstavimo? Tole je primer seznama: <p> 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. </p> <p> -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 <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 unifikacijo). Torej nek -<code>L</code> bi moral postati enak samemu sebi s tem, da bi imel na začetku -še en element. +(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 +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 naredi nov seznam (zgoraj je to -<code>L1</code>). Pa ni to pomnilniško potratno. Je, vendar za to skrbi +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> @@ -201,11 +201,11 @@ prologu seveda ni šlo drugače, preprosto zaradi zasnove jezika. <h2>Kako programiramo s seznami?</h2> <p> -Najbolje, da eno nalogo sprogramiramo skupaj. Naloga naj bo naslednja: predikat +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 vse različne načine. Primer: +element, vstavljen na vsa možna mesta. Primer: </p> <pre> ?- insert(a, [1,2,3], L1). @@ -218,9 +218,9 @@ false. <p> 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. </p> <p> @@ -232,11 +232,11 @@ insert(X, L, L1) :- % procent je oznaka za vrstični komentar v prologu </pre> <p> -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. </p> <pre> insert(X, L, L1) :- @@ -251,7 +251,7 @@ 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> seznam <code>L</code> z +predpostavko prej), potem je <code>L1</code> enak seznamu <code>L</code> z vstavljenim elementom <code>X</code>. Logično! 😊 </p> @@ -262,9 +262,9 @@ 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 +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š +s praznim seznamom, ko ne bo več mogel ničesar odtrgati. Poskusi tole in boš razumel: </p> <pre> @@ -290,13 +290,13 @@ insert(X, [H|T], [H|NT]):- <p> Pomen je enak kot prej, le zapis je veliko krajši. Vse operatorje -<code>=</code> (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 <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: +<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]) @@ -317,9 +317,9 @@ verjetno izračunala rekurzija. </p> <p> -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. </p> </body> |