diff options
Diffstat (limited to 'prolog/problems/lists')
| -rw-r--r-- | prolog/problems/lists/intro_sl.html | 326 | ||||
| -rw-r--r-- | prolog/problems/lists/list.svg | 65 | ||||
| -rw-r--r-- | prolog/problems/lists/sl.py | 5 |
3 files changed, 396 insertions, 0 deletions
diff --git a/prolog/problems/lists/intro_sl.html b/prolog/problems/lists/intro_sl.html new file mode 100644 index 0000000..2b59f5b --- /dev/null +++ b/prolog/problems/lists/intro_sl.html @@ -0,0 +1,326 @@ +<!DOCTYPE html> +<html lang="sl"> +<head> + <meta charset="utf-8" /> + <title>Prolog: seznami</title> + <link rel="stylesheet" type="text/css" href="../style.css" /> +</head> +<body> + +<h1>Prolog: seznami</h1> +<p> +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. +</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 vejico. +</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 unifikacijo). 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 naredi 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 naj bo 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: +</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 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. +</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, 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. +</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> seznam <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 seznamo, 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> (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: +</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, 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. +</p> + +</body> +</html> diff --git a/prolog/problems/lists/list.svg b/prolog/problems/lists/list.svg new file mode 100644 index 0000000..31d73b2 --- /dev/null +++ b/prolog/problems/lists/list.svg @@ -0,0 +1,65 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.38.0 (20140413.2041) + --> +<!-- Title: %3 Pages: 1 --> +<svg width="206pt" height="206pt" + viewBox="0.00 0.00 206.00 206.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 202)"> +<title>%3</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-202 202,-202 202,4 -4,4"/> +<!-- cons0 --> +<g id="node1" class="node"><title>cons0</title> +<text text-anchor="middle" x="63" y="-176.3" font-family="sans" font-size="14.00">·</text> +</g> +<!-- cons1 --> +<g id="node2" class="node"><title>cons1</title> +<text text-anchor="middle" x="99" y="-122.3" font-family="sans" font-size="14.00">·</text> +</g> +<!-- cons0--cons1 --> +<g id="edge2" class="edge"><title>cons0--cons1</title> +<path fill="none" stroke="black" d="M74.7877,-161.973C78.7249,-156.286 83.1141,-149.946 87.0625,-144.243"/> +</g> +<!-- a --> +<g id="node5" class="node"><title>a</title> +<text text-anchor="middle" x="27" y="-122.3" font-family="sans" font-size="14.00">a</text> +</g> +<!-- cons0--a --> +<g id="edge1" class="edge"><title>cons0--a</title> +<path fill="none" stroke="black" d="M51.2123,-161.973C47.2751,-156.286 42.8859,-149.946 38.9375,-144.243"/> +</g> +<!-- cons2 --> +<g id="node3" class="node"><title>cons2</title> +<text text-anchor="middle" x="135" y="-68.3" font-family="sans" font-size="14.00">·</text> +</g> +<!-- cons1--cons2 --> +<g id="edge4" class="edge"><title>cons1--cons2</title> +<path fill="none" stroke="black" d="M110.788,-107.973C114.725,-102.286 119.114,-95.9464 123.063,-90.243"/> +</g> +<!-- b --> +<g id="node6" class="node"><title>b</title> +<text text-anchor="middle" x="63" y="-68.3" font-family="sans" font-size="14.00">b</text> +</g> +<!-- cons1--b --> +<g id="edge3" class="edge"><title>cons1--b</title> +<path fill="none" stroke="black" d="M87.2123,-107.973C83.2751,-102.286 78.8859,-95.9464 74.9375,-90.243"/> +</g> +<!-- empty --> +<g id="node4" class="node"><title>empty</title> +<text text-anchor="middle" x="171" y="-14.3" font-family="sans" font-size="14.00">[ ]</text> +</g> +<!-- cons2--empty --> +<g id="edge6" class="edge"><title>cons2--empty</title> +<path fill="none" stroke="black" d="M146.788,-53.9733C150.725,-48.2862 155.114,-41.9464 159.063,-36.243"/> +</g> +<!-- c --> +<g id="node7" class="node"><title>c</title> +<text text-anchor="middle" x="99" y="-14.3" font-family="sans" font-size="14.00">c</text> +</g> +<!-- cons2--c --> +<g id="edge5" class="edge"><title>cons2--c</title> +<path fill="none" stroke="black" d="M123.212,-53.9733C119.275,-48.2862 114.886,-41.9464 110.937,-36.243"/> +</g> +</g> +</svg> diff --git a/prolog/problems/lists/sl.py b/prolog/problems/lists/sl.py index 9b29fff..0c8dd67 100644 --- a/prolog/problems/lists/sl.py +++ b/prolog/problems/lists/sl.py @@ -1,2 +1,7 @@ name = 'Seznami' description = 'Delo s seznami, poudarek na rekurziji.' +description = '''\ +<p> +<a target="_blank" href="[%@resource intro_sl.html%]">Seznami</a> +– osnovne operacije s poudarkom na rekurziji. +</p>''' |
