Cvičení z Neprocedurálního programování - 5

1-difflist.pl

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

2-trees.pl

% 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?"

3-dfs.pl

% 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 :)