Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Created April 1, 2021 09:31
Show Gist options
  • Save jiribenes/1266f11c9cac19ce9445c951508e85b8 to your computer and use it in GitHub Desktop.
Save jiribenes/1266f11c9cac19ce9445c951508e85b8 to your computer and use it in GitHub Desktop.
Cvičení z Neprocedurálního programování - 5
% Představte si následující dilema:
% Máte odevzdat úkol v Céčku, kde jste si naprogramovali
% jednosměrný spojový seznam, ale nějak moc přistupujete na konec seznamu.
% Abyste vyzráli na ReCodEx, tak si prostě spolu se seznamem udržujete i pointer na poslední prvek.
% Tím pádem můžete dávat na konec seznamu v `O(1)`, testy vám projdou a vše je super.
% Něčemu podobnému v Prologu se říká "rozdílový seznam".
% Vzpomeňte si, že seznam `[1, 2, 3]` se dá v Prologu zapsat také
% jako [1 | [2 | [3 | []]]]. Co kdybychom si udržovali místo prázdného seznamu na konci nějakou proměnnou?
% Máme tedy seznam `[1 | [2 | [3 | Konec]]]`, popřípadě `[1, 2, 3 | Konec]`.
% Nyní nám stačí říct `Konec = 4` a dostaneme `[1, 2, 3, 4]`!
% Takhle je ten trik ale nedostatečný -- nemáme jak ke konci přistoupit.
% Spolu se seznamem si totiž musíme i "venku" udržovat i tu proměnnou na konci:
% `[1, 2, 3 | Konec] - Konec`, obvykle se píše právě takhle.
% Tím pádem můžeme vždycky přistoupit na konec a na něco jej nastavit pomocí unifikace! :)
% Tady jsou dva testovací rozdílové seznamy.
% Dají se použít takhle:
% swipl> testdiff(Seznam), nejakafunkce(Seznam, Vysledek).
testdiff([1,2,3|Konec]-Konec).
testdiff2([a,b,c|DalsiKonec]-DalsiKonec).
% Vyrobíme funkci `diff2list/2`, která z rozdílového seznamu udělá klasický.
diff2list(Seznam-[], Seznam).
% Trochu pomaleji se to dá napsat následovně:
%
% diff2list(Seznam-Konec, Seznam) :- Konec = [].
%
% Slovy: "pokud dostaneš rozdílový seznam s koncem, nastav konec na prázdný seznam".
% Dále vyrobíme funkci `diffpush/3(+RozdilovySeznam, +Prvek, -VyslednyRozdilovySeznam)`,
% která přidá `Prvek` na konec.
diffpush(Seznam-[Prvek|NovyKonec], Prvek, Seznam-NovyKonec).
% Opět, trochu pomaleji to jde napsat takhle:
%
% diffpush(Seznam-Konec, Prvek, Seznam-NovyKonec) :-
% Konec = [Prvek|NovyKonec].
%
% Reálně to dost odpovídá Céčkovému kódu na přidání prvku na konec spojáku. :)
% Nyní chceme funkci
% `diffpend(+Xs, +Ys, -Zs)`
% která spojí dva rozdílové seznamy
% Nechť `A -> B` značí rozdílový seznam `A` s koncem `B`.
% Namalujme si obrázkově co chceme:
%
% Xs -> XEnd
% =
% = Ys -> YEnd
% =
% Zs -> ZEnd
%
% Rovnítko v obrázku znamená unifikaci.
% Dostáváme tedy:
diffpend(Xs-XEnd, Ys-YEnd, Zs-ZEnd) :-
XEnd = Ys,
Zs = Xs,
ZEnd = YEnd.
% Pro fajnšmekry se tahle funkce dá napsat hezky jako:
%
% diffpend(A-B, B-C, A-C).
%
% Na zamyšlení: Nepřipomíná vám to skládání funkcí? ;)
% Není vlastně rozdílový seznam "funkce" typu `List<T> -> List<T>`?
% Pokud si `diffpend` chcete otestovat, zkuste třeba:
% swipl> testdiff(Xs), testdiff2(Ys), diffpend(Xs, Ys, Zs), diff2list(Zs).
% Zs = [1, 2, 3, 4, 5, 6 | Konec] - Konec.
% Zbývá nám převod ze seznamu na rozdílový seznam (rekurzivně):
list2diff([], X-X).
list2diff([H | T], [H | X]-Y) :-
list2diff(T, X-Y).
% Podíváme se na stromy:
% Podobně jako jsme měli "konstruktory" (složené termy) `nil` a `cons(X, Y)` pro
% naše homemade spojové seznamy, teď máme podobné pro binární stromy
%
% popis: větvička s X ve vrcholu (prázdný) list stromu
%
% term: t(L, X, R) nil
%
% obrázek: X (x)
% / \
% L R
%
% Příklad:
%
% 42 = t(t(nil, 1, nil), 42, t(nil, 100, nil))
% / \
% 1 100
% Zase můžete použít následující na testování:
% swipl> treetest(Tree), funkcepracujicisestromem(Tree, Vysledek).
treetest(t(t(t(nil, 2, nil), 3, t(nil, 4, nil)), 5, t(nil, 8, t(nil, 9, nil)))).
% Uděláme si funkci, která vrátí, jestli je `X` vrchol stromu:
% treeElem(X, Strom) :- X je člen stromu
treeElem(X, t(L, _, _)) :-
treeElem(X, L).
treeElem(X, t(_, X, _)).
treeElem(X, t(_, _, R)) :-
treeElem(X, R).
% Rozmyslete si, že pořadí těchto klauzulí přímo určuje,
% jestli je průchod pre/in/post-order :)
% Hloubka stromu:
treeDepth(nil, 0).
treeDepth(t(L, _, R), Hloubka) :-
treeDepth(L, HloubkaL),
treeDepth(R, HloubkaR),
Hloubka is 1 + max(HloubkaL, HloubkaR). % `max/2` je aritmetická instrukce, podobně jako `+`.
% Velikost stromu:
treeSize(nil, 0).
treeSize(t(L, _, R), Velikost) :-
treeSize(L, VelikostL),
treeSize(R, VelikostR),
Velikost is 1 + VelikostL + VelikostR.
% Nyní vyrobíme funkci, která vezme strom
% a vrátí seznam jeho vrcholů dle inorder průchodu.
treeTraverseSlow(nil, []).
treeTraverseSlow(t(L, X, R), Result) :-
treeTraverseSlow(L, ResultL),
treeTraverseSlow(R, ResultR),
append(ResultL, [X|ResultR], Result). % Result = ResultL ++ [X] ++ ResultR
% Rozmyslete si jak funkci upravit, aby průchod byl postorder nebo preorder.
% Tahle funkce je ale šeredně pomalá! (viz ten zlý O(N) append!)
% Udělejme to pořádně a s akumulátorem.
treeTraverse(Tree, Result) :-
treeTraverse_(Tree, [], Result). % Počáteční akumulátor je prázdný seznam.
% Pokud jsme v listu, vrátíme akumulátor
treeTraverse_(nil, Acc, Acc).
treeTraverse_(t(L, X, R), Acc, Result) :-
% Nejprve projdeme *pravý* podstrom s akumulátorem `Acc`, což vrátí `AccR`.
treeTraverse_(R, Acc, AccR),
% Pak přidáme `X` do `AccR`, čímž získáme nový akumulátor
NewAcc = [X|AccR],
% Projdeme levý podstrom.
treeTraverse_(L, NewAcc, Result).
% Teď už nemáme žádný zlý O(N) append! :)
% Rozmyslete si, že to co děláme je správně i přes to,
% že nejprve procházíme *pravý* strom.
% (Hint: Přesvědčte se, že `Result` bude mít prvky ve správném pořadí)
% Nyní chceme funkci `treeSum(Tree, Sum)`, která sečte prvky ve vrcholech stromu.
treeSum(nil, 0).
treeSum(t(L,X,R), Sum) :-
treesum1(L, SumL),
treesum1(R, SumR),
Sum is X + SumL + SumR.
% Připomínka funkce `fold` z minule:
fold(_, [], _) :- fail.
fold(_, [X], X).
fold(Fn, [A, B | Tail], Result) :-
call(Fn, A, B, Acc),
fold(Fn, [Acc | Tail], Result).
% Skoro stejná funkce se jmenuje `foldl/4` v SWI Prologu.
% Pomocná definice součtu:
add(X, Y, Z) :- Z is X + Y.
% `treeSum` pomocí foldu :)
treeSumFold(Tree, Sum) :-
treeTraverse(Tree, List),
fold(add, List, Sum). % sumall(List, Sum) :- fold(add, List, Sum).
% Odbočka: jak poznat, že je seznam setřízený?
listIsSorted([]).
listIsSorted([_]).
listIsSorted([A, B | Tail]) :-
A =< B, % pozor, v Prologu se píše "menší rovno" jako `=<` ("rovno menší")
listIsSorted([B | Tail]).
% Galaxy brain verze pomocí foldu:
mensirovno(A, B, B) :- A =< B.
listIsSortedBigBrain(List) :-
fold(mensirovno, List, _).
% Opravdu se zamyslete nad tím, proč/jak to vlastně funguje!
% Je strom BVS?
treeIsSorted(Tree) :-
treeTraverse(Tree, List),
listIsSorted(List).
% Vlastně využíváme toho, že: "Je strom BVS?" <=> "Je inorder průchod seřazený list?"
% Vezmeme si skoro stejný graf jako na úplně prvním cvičení:
% /---------------\
% | \
% \/ \
% A <------> B ---> C
% \ \ /|
% \| \| /
% E----------->F
% \ /|
% \| /
% D /
% /| /
% / /
% G ---> H
edge(a, b).
edge(a, e).
edge(b, a).
edge(b, c).
edge(b, f).
edge(c, a).
edge(e, d).
edge(e, f).
edge(f, c).
edge(g, d).
edge(g, h).
edge(h, f).
% Napíšeme si příjemné malé DFS:
% dfs(+Start, +Goal, +Visited, -Path).
% Pokud jsme v cíli, zajásej a přidej jej do výsledné cesty.
dfs(Start, Start, _, [Start]).
% Pokud ne, potom přidej `Start` do výsledné cesty, jestliže:
dfs(Start, Goal, Visited, [Start | Path]) :-
edge(Start, V), % Vede hrana mezi `Start` a vrcholem `V`
\+ member(V, Visited), % & `V` nebyl ještě navštíven
dfs(V, Goal, [V | Visited], Path). % & dokážeš se dostat z `V` do cíle
% Top-level funkce na volání DFS, nastaví `Visited` na `[Start]`.
dfs0(Start, Goal, Path) :- dfs(Start, Goal, [Start], Path).
% Co kdybychom chtěli DFS do zadané hloubky?
% Na to nám stačí něco jako:
dfsExactDepth(Start, Goal, ExactDepth, Path) :-
length(Path, ExactDepth),
dfs0(Start, Goal, Path).
% Co kdybychom chtěli postupně prohlubovat DFS?
% Jít nejprve do hloubky 1, pak do hloubky 2, atd.
% Na to si všimneme, jak se chová `length(-List, -Length)`:
% swipl> length(Path, _).
% Path = [] ;
% Path = [_3610] ;
% Path = [_3610, _3616] ;
% Path = [_3610, _3616, _3622] ;
% Path = [_3610, _3616, _3622, _3628]
% ...
% On nám vlastně generuje seznamy!
% Takže na iterativní prohlubování nám stačí tohle:
iterDeep(Start, Goal, Path) :-
length(Path, _),
dfs0(Start, Goal, Path).
% No a je to!
% Jako příklad si můžete zkusit nějaké klasické prohledávání stavového grafu
% ve stylu problému "převozník, koza a zelí".
% Alternativně to můžete použít v domácím úkolu :)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment