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

0-warmup.prolog

%%% Příklady na rozcvičení (tohle byste měli zvládnout sami):

% 1. Napište predikát `same_length(?L1, ?L2)`,
% který uspěje ve chvíli, kdy jsou oba seznamy stejně dlouhé.
% Nepoužívejte aritmetiku.

% 2. Napište predikát `middle(+L, ?M)`,
% který uspěje, pokud je `M` prvek uprostřed seznamu.
% Nepoužívejte aritmetiku!
%
% Nápověda: vyrobte si `middle(+L1, +L2, ?M)`,
% kde v jednom seznamu skáčete po dvou prvcích a v druhé po jednom prvku.
% Poté volejte následovně `middle(L, M) :- middle(L, L, M)`.

same_length([], []).   % prázdný seznam je stejně dlouhý pouze jako prázdný seznam (je to jediný seznam délky 0).
same_length([_ | Tail1], [_ | Tail2]) :-  % seznamy jsou stejně dlouhé
  same_length(Tail1, Tail2).              % pokud jsou jejich ocásky stejně dlouhé
  
  
middle(List, Mid) :-
  middle(List, List, Mid).
  
% pomocný predikát
% Mimochodem, všimněte si, že predikáty mohou mít jinou implementaci
% v závislosti na počet argumentů, který dostanou ;)

middle([Mid | _]  [], Mid).      % Pokud v druhém seznamu nic nezbylo, pak začátek prvního seznamu je prostředek.
middle([Mid | _], [_], Mid).     % Pokud v druhém seznamu zbyl jediný prvek, pak začátek prvního seznamu je prostředek.
middle([_ | Tail1], [_, _ | Tail2], Mid) :- % v prvním seznamu skáčeme po jednom prvku, v druhém po dvou prvcích
  middle(Tail1, Tail2, Mid).                % a voláme rekurzivně zbytek :)
  
%% Poznámka:
% V Prologu píšeme do dokumentace jestli je argument pouze vstupní, to značíme pomocí +,
% nebo pouze výstupní, to značíme pomocí `-`,
% nebo obojí, což značíme pomocí `?`.

1-reverse.prolog

%% Tato funkce otočí spojový seznam

% Tahle funkce je technicky O(N^2), jde to i lineárně, jak uvidíme za chvilku :)
% 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, TailResult, Result),        % Result = Head + TailResult
    soucet(Tail, TailResult).

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

% 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

% Protože Prolog podporuje uživatelsky definované operátory,
% tak `1 + 2` vlastně není nic jiného než `+(1, 2)`.
% swipl> +(1, 2) = 1 + 2
% true.

% 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-seznam.prolog

% Tato funkce byla zadána jako hádanka:

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

% Spoiler: `foo` rozdělí seznam na prvky se sudými a lichými členy.

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

% Pozor, že se `smaz` chová trochu zvláštně, pokud je v seznamu více stejných prvků, které hledáme.
% ?- select(2,[1,2,3,2,4],R).
% R = [1, 3, 2, 4] ;
% R = [1, 2, 3, 4] ;
% false.

4-map.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]