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

1-graf.prolog

% Bavili jsme se o unifikaci a backtrackingu....

% `X = Y` v prologu znamená "unifikuj X a Y"
%
% například:
% ?- f(X, g(Y)) = f(g(z), X).
% X = g(z),
% Y = z.
%
% Všimněte si, že Prolog vrací nejobecnější možné dosazení :)

% Pak jsme se bavili o tom, že Prolog je vlastně jen DFS s backtrackingem + unifikace!

% Pokračování grafů z minulého cvičení:
%
%  A  ------> B   ---> C
%  \            \    /|
%   \|           \| /  
%    E----------->F 
%    \           /|
%     \|        /
%      D       /
%     /|      /
%    /       /
%    G ---> H


edge(a, b).
edge(a, e).
edge(b, c).
edge(b, f).
edge(e, d).
edge(e, f).
edge(f, c).
edge(g, d).
edge(g, h).
edge(h, f).

% Chceme definovat 'path(U, V)', který značí jestli existuje orientovaná cesta z U do V
% Hranu z U do V značím jako U -> V
% Orientovanou cestu z U do V značím jako U ~~~> V

% Níže jsou definovány tři varianty:
% * `path` je verze z prvního cvičení - najde výsledek a nezacyklí se
% * `path2` je nová verze - sice najde výsledek, ale zacyklí se
% * `path3` je nová verze - jen se zacyklí
% Hlavně jsme řešili rozdíl mezi "deklarativní správností", cca "formule daná pravidlem je správně"
% versus "procedurální správností", cca "dá správný výsledek"

% funguje z minulého cvičení
path(U, U).
path(U, V) :- edge(U, W), path(W, V).

% najde výsledek a pak se zacyklí
path2(U, U).
path2(U, V) :- path2(W, V), edge(U, W).

% zacyklí
path3(U, V) :- edge(U, W), path3(W, V).
path3(U, U).

2-peano.prolog

% Můžeme si vytvořit složené termy

% Nepotřebujeme dopředu definovat tvar takových termů,
% narozdíl od Céčka, kde bychom museli napsat `struct pair { int a; int b; }`

% Vrátí první, resp. druhý člen dvojice.
% `_` znamená "Vytvoř novou proměnnou, která je různá od
% všech již existujících proměnných"
first(pair(A, _), A).
second(pair(_, B), B).

%% unární reprezentace čísel
%% Taky se ji říká Peanova aritmetika (či Robinsonova)
% 0 značí nulu
% s(X) značí následníka čísla X, tedy X + 1

% nat: je něco číslo?
nat(0).                % 0 je číslo
nat(s(X)) :- nat(X).   % (X + 1) je číslo, pokud X je číslo

% Příklady čísel:
% zero = 0.
% one = s(0). % successor of 0
% two = s(s(0)).
% three = s(s(s(0))).

% Chceme zadefinovat sčítání:
% add(X, Y, Z)

% 0 + X = X
add(0,X,X) :- nat(X).

% (X + 1) + Y = (Z + 1)  if X + Y = Z
add(s(X), Y, s(Z)) :-
    nat(X), nat(Y), nat(Z),
    add(X, Y, Z).

% Tracujeme ručně `add(1,2,A)`:
%   add(1, 2, A)
% = add(s(0), s(s(0)), A)
%   ~> basecase
%     <~ no.
%   ~> X = 0, Y = s(s(0)), A = s(Z)
%     ~> add(0, s(s(0)), Z)
%       ~> basecase: X' = s(s(0)), Z = X'
%
%  X = 0, Y = s(s(0)), X' = s(s(0))
%
%  A = s(Z) = s(X') = s(s(s(0))).
% Doporučuji si výše uvedené vytraceovat i v REPLu

% Cvičení: Zkuste jednu z proměnných dát volnou, co se stane?
% Co když dáte dvě proměnné volné?
% Konkrétně co se stane když dáte `add(X, Y, s(s(s(s(0)))))`? (to poslední číslo je 4)
% Ideálně by vám to vypsalo všechna X a Y taková, že X + Y = 4.
% Jenže ono se to po chvilce zacyklí -- proč?


% Násobení
% mult(X, Y, Z)
% basecase
mult(0,X,0).

% Rozmyslete si, že tenhle basecase vlastně není potřeba
mult(s(0),X,X).

% rekurzivní případ
% (X + 1) * Y = (X*Y) + Y = M + Y = Z
mult(s(X), Y, Z) :-
    mult(X, Y, M),   % X * Y = M
    add(M, Y, Z).    % M + Y = Z
    
% Cvičení: Vytvořte `less_equal(X, Y)`, který platí pokud X <= Y,
% kde X, Y jsou čísla zadaná v Peanově aritmetice

% Cvičení: Vytvořte dělení dvěma -- `divTwo(X, Y)`, tedy Y := X / 2 (celočíselně).
% Uměli byste i obecné celočíselné dělení -- `div(X, Y, Z)`?

3-seznam.prolog

% Dál jsme se vrhli na seznamy
% a rovnou jsme se rozhodli si vyrobit vlastní složené termy,
% které reprezentují seznam.

% nil                     .... prázdný seznam
% cons(X, Y)              .... X je hlava seznamu [head]
%                            , Y je tělo (ocásek) [tail]
% 

% Predikát `list(X)` značí jestli `X` je seznam.
list(nil).                        % prázdný seznam je seznam
list(cons(Head, Tail)) :-         % dvojice (Head, Tail) je seznam iff Tail je seznam
  list(Tail).

% příklad seznamu [1, 2, "test"]
% cons(1, cons(2, cons("test", nil)))

% `printlist(X)` vypíše obsah stringového seznamu.
% (To, že obsahuje stringy nikde nekontrolujeme)
printlist(nil).
printlist(cons(String, Tail)) :-
    writeln(String),
    printlist(Tail).

% Můžeme si představit, že Prolog uvnitř funguje následovně:
% (Opravdové seznamy v Prologu    vs.   ty naše custom seznamy)
%
% [] ~~~> nil
% [1, 2, 3] ~~~> cons(1, cons(2, cons(3, nil)))
% [Head|Tail] <~~~ cons(Head, Tail)

% `printlist`, jen pro seznamy se syntaktickým cukrem.
printlist2([]).
printlist2([String|Tail]) :-
    writeln(String),
    printlist2(Tail).

% Doopravdy to je tak, že Prolog podporuje operátory a má:
% * nulární operátor []                 ... reprezentuje náš `nil`
% * binární operátor [X|Y]              ... reprezentuje náš `cons(X, Y)`
%
% Potom následující notace jsou ekvivalentní:
% [1, 2, "test"]
% cons(1, cons(2, cons("test", nil)))   ... pozor, tahle notace je jen naše, nebude fungovat na predikáty v Prologu
% [1|[2|["test"|[]]]]                   ... explicitně napsaný [1, 2, "test"] pomocí operátorů        

% Tohle by mělo být `true`, je to takový důkaz, že nekecám. :)
stejny :- [1, 2, "test"] = [1|[2|["test"|[]]]].

% náleží prvek seznamu?
% standardně ve std knihovně jako `member/2`, tedy funkce `member`, která bere 2 argumenty
elem(X, [X|_]).
elem(X, [_|T]) :- elem(X, T).

% Tahle verze `elem` skáče po dvou prvcích
% elem(X, [X, _|_]).
% elem(X, [_, _|T]) :- elem(X, T).

% Jak namatchovat správný seznam:
% f([A, B])            ... uspěje pro seznamy délky 2
% f([A, B | Tail])     ... uspěje pro seznamy délky >=2

% Hádanka, co dělá tahle funkce?
foo([], X, X).
foo([H|T], Y, [H|R]) :- foo(T, Y, R).
% standardně se jmenuje append/3 ;)