Cvičení z Neproceduráního programování - 3

1-tco.prolog

% V předchozím díle jste viděli:

% Otočí spojový seznam
% Tahle funkce je technicky O(N^2), jde to i lineárně, jak uvidíme příště. :)
% V knihovně ji najdete jako `reverse/2`.
otoc([], []).
otoc([Head|Tail], Result) :- 
    otoc(Tail, ReversedTail),             % ... otočíme ocásek
    append(ReversedTail, [Head], Result). % ... na konec otočeného ocásku připneme jednoprvkový seznam `[Head]`
                                          %     a výsledek označíme jako `Result`.

% %%% trace:
%   otoc([1, 2, 3], Result)
%     ~> otoc([2, 3], ReversedTail)
%        ...
%     ~> append(ReversedTail, [1], Result)   % připojení prvku na konec spojáku ... O(N)

% Napíšeme teď verzi s ocáskovou rekurzí/s akumulátorem:

% Všimněte si, že na konci nepropagujeme žádnou informaci zpátky -- rekurze tím efektivně končí!
otoc_rychle([], Pamet, Pamet).
otoc_rychle([Head|Tail], Pamet, Result) :-
    NovaPamet = [Head|Pamet],                % připojení prvku na začátek spojáku ... O(1)
    otoc_rychle(Tail, NovaPamet, Result).
% Ještě si všimněte, že jdeme vždy deterministicky.
% Chytrý překladač by tohle mohl rovnou přeložit na jediný for/while loop
% bez rekurze.

% %%% trace:
%   otoc_rychle([1, 2, 3], [], Result)
%      ~> NovaPamet = [1]
%      ~> otoc_rychle([2, 3], NovaPamet, Result)
%          ~> NovaPamet' = [2, 1]
%          ~> otoc_rychle([3], NovaPamet', Result)
%              ~> NovaPamet'' = [3, 2, 1]
%              ~> otoc_rychle([], NovaPamet'', Result)
%                    ~> Result = NovaPamet''
%   => Result = [3, 2, 1]

% Napíšeme si predikát `delka`, který vrátí délku seznamu
% v Peanově aritmetice (viz předchozí přednáška).

% `delka` vrací délku seznamu v Peanově aritmetice
delka(Xs, R) :- delka_(Xs, 0, R).

% delka_(+Xs, +Acc, -R)
delka_([], Acc, Acc).

% delka_([_|Xs], Acc, Result) :- delka_(Xs, Acc + 1, Result).
delka_([_|Xs], Acc, Result) :- delka_(Xs, s(Acc), Result).

% Predikát `soucet` sečte všechny členy seznamu.
soucet([], 0).
soucet([Head|Tail], Result) :-
    add(Head, Result, NewResult),        % NewResult = Head + Result
    soucet(Tail, NewResult).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Pomocné deklarace k Peanově aritmetice z minula:

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

% 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)) :-
    add(X, Y, Z).

2-arith.prolog

% Aritmetika:
%
% Nejprve si rozmyslete, že syntakticky je následující výraz:
%                 (1 + 2) * 3
%
% v podstatě jen tenhle strom:
%                         *
%                        / \
%                       +   3
%                      / \
%                     1   2
%

% Když do swipl-u napíšete
% swipl> X = 1 + 2
% tak vám odpoví
% X = 1 + 2

% Podobně:
% swipl> X = (1 + 2) * 3
% X = (1 + 2) * 3

% To je proto, že Prologovské rovnítko `=` je unifikace.
% My ale chceme operaci "vyhodnoť a ulož do".
% Na to se dá použít operátor `is`!

% swipl> X is 1 + 2
% X = 3

% swipl> X is (1 + 2) * 3
% X = 9

% Co když tedy budeme chtít napsat součet
% s "opravdovou" aritmetikou?

% Nejprve zapomeňme na to, že existuje `is`.
soucetBezIs(Xs, Result) :-
    soucetBezIs_(Xs, 0, Result).

% zase používáme akumulátor
soucetBezIs_([], Acc, Acc).
soucetBezIs_([H|T], Acc, Result) :-
    NewAcc = H + Acc,
    soucetBezIs_(T, NewAcc, Result).

% Nyní když zavoláme `soucetBezIs`, tak se `NewAcc` bude nastavovat
% jen syntakticky, bez vyhodnocení. Tedy:
% swipl> soucetBezIs([1, 2, 3], X).
% X = (3 + (2 + (1 + 0)))

% To ale nechceme :(

% Zkusme tedy napsat verzi s `is`:
soucet(Xs, Result) :-
    soucet_(Xs, 0, Result).

soucet_([], Acc, Acc).
soucet_([H|T], Acc, Result) :-
    NewAcc is H + Acc,
    soucet_(T, NewAcc, Result).
    
% swipl> soucet([1, 2, 3], X).
% X = 6
% Mnohem lepší! :)

% Cvičení: Napište predikát, které vezme číslo v Peanově aritmetice
% a vrátí číslo v běžné aritmetice, třeba: s(s(s(0))) ~~~> 3
% Další cvičení: Napište i opačný predikát. :)

% Faktoriál s ocáskovou rekurzí:
% počáteční akumulátor je `1`
fakt(X, Y) :- fakt_(X, 1, Y).

fakt_(1, Y, Y).
fakt_(X, Acc, Y) :-
    X > 1,               % defenzivně kontrolujeme, že nám někdo nedal číslo menší než 1 :)
    NewAcc is Acc * X,
    NewX is X - 1,
    fakt_(NewX, NewAcc, Y).

3-seznamy.prolog

% Tyto funkce byly jako hádanky:

foo([], [], []).
foo([A], [A], []).
foo([A, B|R], [A|L], [B|P]) :-
    foo(R, L, P).

bar([], []).
bar([_|A], [_|B]) :- bar(A, B).

% Spoiler: `foo` rozdělí seznam na prvky se sudými a lichými členy.
% Spoiler: `bar` zkontroluje, že dva seznamy mají stejný počet prvků.


%%%%%%%%%%%


% Najdi prostředek seznamu (bez aritmetiky!)
prostredek(S, X) :- prostredek_(S, S, X).

% prostredek_:
%  - První argument skáče po dvou
%  - Druhý argument skáče po jednom
%  - Pokud se první argument dostal na konec, pak druhý je v půlce!
prostredek_([], [X|_], X).
prostredek_([_], [X|_], X).
prostredek_([_,_|Xs], [_|Ys], Result) :-
    prostredek_(Xs, Ys, Result).

% smaz(X, Xs, R)
% smaže X v Xs a vrátí výsledek v R
% smaz(a, [a, b, c, d, e], R) ~> R = [b, c, d, e].
%
% select/3 ve std knihovně
smaz(X, [X|Xs], Xs).
smaz(X, [Y|Ys], [Y|Zs]) :- smaz(X, Ys, Zs).

4-maplist.prolog

% vynasobDvema(+Xs, -Result)
% vynasobi kazdy prvek dvojkou

vynasobDvema([], []).
vynasobDvema([X | Xs], [Y | Result]) :-
    Y is 2*X,                                 % ekvivalentní `kratDva(X, Y)`
    vynasobDvema(Xs, Result). 

% pomocná funkce
kratDva(X, Y) :- Y is X * 2.

% Všimněte si, že tohle je častý pattern:
% "Na každý prvek seznamu aplikuj funkci".


% V Pythonu to vypadá následovně:
%
% def foo(xs):
%    result = []
%    for x in xs:
%        result.append( f(x) )
%    return result


% Napíšeme si tedy funkci, která tohle umí abstrahovat:
% `mapa` (ve std knihovně jako `maplist/3`)

% mapa<t, u>(+Xs : [t], +Fn : t -> u, -Ys : [u]).
% ^ Tady jsem napsal i "typy", které očekáváme.
% Nijak je nekontrolujeme, ale jako dokumentace se to IMO hodí :)
mapa([], _, []).
mapa([Head | Tail], Fn, [NewHead | NewTail]) :-
    call(Fn, Head, NewHead),        % explicitně zavoláme `Fn` na `Head` a získat `NewHead` pomocí `call/3`
    mapa(Tail, Fn, NewTail).

% swipl> mapa([1, 2, 3], kratDva, X)
% X = [2, 4, 6]

prictiJedna(X, Y) :- Y is X + 1.

% swipl> mapa([1, 2, 3], prictiJedna, X)
% X = [2, 3, 4]