From 8bbd19d74c1be8f19888556be1894482abb1b7d5 Mon Sep 17 00:00:00 2001 From: Timotej Lazar Date: Thu, 10 Mar 2016 15:55:58 +0100 Subject: Prolog: add intro text for lists exercises --- prolog/problems/lists/intro_sl.html | 326 ++++++++++++++++++++++++++++++++++++ 1 file changed, 326 insertions(+) create mode 100644 prolog/problems/lists/intro_sl.html (limited to 'prolog/problems/lists/intro_sl.html') 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 @@ + + + + + Prolog: seznami + + + + +

Prolog: seznami

+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. +

+ +

Kako izgledajo seznami v prologu?

+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. +

+ +

+ +

+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:

v seznamih je lahko karkoli;
dostopaš vedno do glave seznama (ali več glav), do repa se moraš + (rekurzivno) prebiti;
na zapis [H|T] glej kot na primerjanje vzorcev;
ne razmišljaj o porabi pomnilnika, za to skrbi garbage collection;
glava seznama je poljubnega tipa, medtem, ko je rep seznama vedno seznam.

+ +

Kako programiramo s seznami?

+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. +

+ + + -- cgit v1.2.1