From a9416de1d2bde1b2327928717d00d262160912af Mon Sep 17 00:00:00 2001 From: Timotej Lazar Date: Thu, 17 Mar 2016 13:59:10 +0100 Subject: Prolog: tweak intro text for lists exercises --- prolog/problems/lists/intro_sl.html | 66 ++++++++++++++++++------------------- 1 file changed, 33 insertions(+), 33 deletions(-) (limited to 'prolog/problems') 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 @@

Prolog: seznami

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

Kako izgledajo seznami v prologu?

@@ -26,11 +26,11 @@ Torej, kako sezname v prologu zapišemo, predstavimo? Tole je primer seznama:

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

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

@@ -201,11 +201,11 @@ prologu seveda ni šlo drugače, preprosto zaradi zasnove jezika.

Kako programiramo s seznami?

-Najbolje, da eno nalogo sprogramiramo skupaj. Naloga naj bo naslednja: predikat +Najbolje, da eno nalogo sprogramiramo skupaj. Naloga je 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: +element, vstavljen na vsa možna mesta. Primer:

 ?- insert(a, [1,2,3], L1).
@@ -218,9 +218,9 @@ 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. +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.

 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! 😊
 

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

@@ -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 predikat insert/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 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])
@@ -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.

-- cgit v1.2.1