1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
name = 'conc/3'
slug = 'Združi dva seznama (konkatenacija)'
description = '''\
<p><code>conc(?L1, ?L2, ?L)</code>: seznam <code>L</code> dobiš tako, da seznamu <code>L1</code> na konec dodaš elemente seznama <code>L2</code>.</p>
<pre>
?- conc([1,2], [3,4], X).
X = [1,2,3,4].
?- conc(X, [], [1,2,3]).
X = [1,2,3].
</pre>'''
plan = ['''\
<p><img src="[%@resource plan.svg%]" /></p>
''', '''\
<p>Začnimo z enostavnim vprašanjem: kaj bi bil rezultat, če konkateniram prazen seznam in seznam <code>L2</code>?</p>
''', '''\
<p>Sedaj recimo, da ima prvi seznam točno en element. Začasno ga vzemimo stran, ostali smo s praznim prvim seznamom.
Kaj ni ta situacija podobna oni od prej? Seveda, problem smo zmanjšali za en element in ga tako prevedli na manjši
problem! Uporabimo rekurzijo za rešitev tega manjšega problema. A na koncu ne pozabimo rezultat rekurzije ustrezno
dopolniti s prej odvzetim prvim elementom...</p>
''', '''\
<p>Deklarativno/logično razmišljanje: Recimo, da ima prvi seznam <code>L1</code> glavo <code>H</code> in rep
<code>T</code>. Če je (rekurzivni) rezultat konkatenacije <code>T</code> in <code>L2</code> nek seznam
<code>L3</code> in če seznamu <code>L3</code> na začetek dodam element <code>H</code>, kaj s tem dobim?
Konkatenacijo seznamov <code>L1</code> in <code>L2</code>!</p>
''']
hint = {
'eq_instead_of_equ': '''\
<p>Operator <code>==</code> je strožji od operatorja <code>=</code> v smislu, da je za slednjega dovolj,
da elementa lahko naredi enaka (unifikacija). Morda z uporabo <code>=</code> narediš predikat
<code>conc/3</code> delujoč tudi v kakšni drugi smeri.</p>
<p>Seveda pa lahko nalogo rešiš brez obeh omenjenih operatorjev, spomni se, da lahko unifikacijo narediš
implicitno že kar v argumentih predikata (glavi stavka).</p>
''',
'eq_instead_of_equ_markup': '''\
<p>Morda bi bil bolj primeren operator za unifikacijo (=)?</p>
''',
'base_case': '''\
<p>Si pomislil na robni pogoj? Kaj je najbolj enostaven primer?
Kaj bi bil, recimo, rezultat, če je prvi seznam kar prazen? (Samo prvi seznam naj bo prazen,
v drugem seznamu je lahko karkoli.)</p>
''',
'base_case_arbitrary': '''\
<p>Kako je lahko rezultat konkatenacije seznamov poljuben seznam oz. karkoli?</p>
<p>Če je tvoj robni pogoj podoben <code>conc([], L, _)</code>,
ga še enkrat premisli: kaj je rezultat konkatenacije, kaj vračaš? Robni pogoj je vedno dokončno specificirana
rešitev, tu načeloma ni neznank (<code>_</code> ali spremenljivk brez prirejenih vrednosti) v tem kar se vrača.</p>
''',
'predicate_always_false': '''\
<p>Vse kaže, da tvoj predikat vedno vrne "false". Si mu dal pravilno ime, si se morda pri imenu zatipkal?</p>
<p>Če je ime pravilno, se morda splača preveriti tudi, če se nisi zatipkal kje drugje,
je morda kakšna pika namesto vejice ali obratno, morda kakšna spremenljivka z malo začetnico?</p>
<p>Možno je seveda tudi, da so tvoji pogoji prestrogi ali celo nemogoči (kot bi bila npr. zahteva,
da je <code>X</code> hkrati starš in sestra od <code>Y</code> ali kaj podobno zlobnega).</p>
''',
'timeout': '''\
<p>Je morda na delu potencialno neskončna rekurzija? Kako se bo ustavila?</p>
<p>Morda pa je kriv tudi manjkajoč, neustrezen ali preprosto nekompatibilen (s splošnim primerom) robni pogoj?
Morda npr. v rekurziji zmanjšuješ prvi seznam, ustaviš pa se pri praznem drugem seznamu (ali obratno)?</p>
''',
'second_list_iteration': '''\
<p>Kot kaže zmanjšuješ in "obdeluješ" drugi seznam. Mehanizem je pravi, ampak vrstni red na koncu pa ni.
Raje zmanjšuj prvi seznam in pusti drugega kot je.</p>
<p>Pa še drug razlog za ta vrstni red je: tako bomo vsi imeli enako, standardno, rešitev in bomo
<code>conc/3</code> uporabljali na enak način. To je zelo pomembno za kasneje.</p>
''',
'insertion_into_second_list': '''
<p>Je tvoj rekurzivni klic oblike <code>conc(T, [H|L2], ...)</code>? Ne vstavljaj glave prvega seznama v
drugi seznam v rekurzivnem klicu, to ti bo dalo napačen vrstni red. Pusti rekurziji, da sama poskrbi
za združevanje repa prvega seznama <code>T</code> z drugim seznamom <code>L2</code>, potem pa
(ob vračanju rezultata) dodaj glavo prvega seznama <code>H</code> na pravo mesto.</p>
''',
'two_heads': '''\
<p>Res potrebuješ dve glavi? Poskušaš morda zmanjševati hkrati oba seznama? To ni dobra ideja, tako boš
res težko prišel do pravilne rešitve. Raje zmanjšuj samo prvi seznam in pusti drugega kot je.</p>
''',
'two_heads_markup': '''\
<p>Res potrebuješ dve glavi?</p>
''',
'forcing_result_onto_recursion': '''
<p>Ne vsiljuj rekurziji kaj naj vrne, prepusti se ji. To je tisti del, ko narediš predpostavko,
če je ta izpolnjena, potem bo tvoje pravilo delovalo za večji primer.</p>
<p>Je tvoj rekurzivni klic oblike <code>conc(T, L2 [H|...])</code>? S tem vsiljuješ rekurziji
da mora <emph>vrniti</emph> tudi glavo, ki si jo prej že dal začasno stran. Glavo moraš na koncu na primerno mesto
vstaviti ti. Skratka, glavo <code>H</code> dodaj izven rekurzivnega klica.</p>
''',
'final_hint': '''\
<p>Predikat <code>conc/3</code> bomo večinoma uporabljali za vse drugo kot samo za konkatenacijo dveh seznamov.
Med drugim je uporaben "v obratni smeri" za delitev seznama na dva dela, poskusi naslednja vprašanja:</p>
<p><code>?- conc(L1, L2, [a,b,c,d]).</code></p>
<p><code>?- conc([X,Y], L2, [a,b,c,d,e,f]).</code></p>
<p>Si opazil, da je drugo vprašanje v bistvu vrnilo prva dva elementa iz seznama <code>[a,b,c,d,e,f]</code>?</p>
<p>Nadalje je <code>conc/3</code> uporaben za iskanje vzorcev v seznamu, npr. takole:</p>
<p><code>?- conc(_, [X,X|_], [a,b,c,c,d,e,f,f,g,h,h]).</code></p>
<p>Tako je, to vprašanje najde vse možnosti, kjer se dva elementa ponovita drug za drugim v seznamu (vzorec X,X).
V bistvu smo rekli "nekaj poljubnih elementov (lahko tudi nič) je spredaj, potem sta dva enaka, potem pa spet nekaj
poljubnih elementov (lahko nič) zadaj."
Še veliko drugih koristi bo od <code>conc/3</code>, jih boš že še sproti spoznal.</p>
''',
}
|
