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

1-rezy.pl

% Minule jsme se bavili o funkci, která smaže všechny výskyty prvku,
% ale nechali jsme ji na dnešek.
% Chceme tedy funkci smazVsechny(X, S, R), která smaže všechny výskyty X ze seznamu S.
% První implementace může vypadat takhle:
smazVsechny(_, [], []).

smazVsechny(X, [X|XS], R) :-
    smazVsechny(X, XS, R). 

smazVsechny(X, [Y|YS], [Y|R]) :-
    smazVsechny(X, YS, R).
    
% To ale není úplně správně:
% swipl> smazVsechny(a, [a, b, c, a, d], X).
% R = [b, c, d] ;
% R = [b, c, a, d] ;
% R = [a, b, c, d] ;
% R = [a, b, c, a, d] ;
% false.

% Tedy nám to vrací špatné odpovědi! :(

% Použijeme tedy *řez* představovaný operátorem `!`, který Prolog vyděsí natolik,
% že pokud přes něj přejde, tak už se za něj nevrátí.
% V řeči backtrackingu: Nebacktrackuje se za vykřičník.

% Funkci tedy můžeme opravit následovně
smazVsechny(_, [], []).

smazVsechny(X, [X|XS], R) :-
    !,                    % pokud jsme se dostali sem, pak nechceme backtrackovat
    smazVsechny(X, XS, R). 

smazVsechny(X, [Y|YS], [Y|R]) :-
    smazVsechny(X, YS, R).

% Jiný příklad:
% Pokud si chceme zadefinovat maximum ze dvou čísel, tak naivně je to následovně:

max(A, B, B) :- A < B.
max(A, B, A) :- A >= B.

% Jen to není efektivní -- pokud uspěje první klauzule a rozhodneme se
% backtrackovat, pak zkoušíme zbytečně druhou klauzuli, která nemůže uspět!

max2(A, B, B) :- A < B, !.
max2(A, B, A) :- A >= B.

% Řešením je tedy přidat řez ^.

% Řezu v `smazVsechny` se říká "červený", protože mění význam programu,
% zatímco ten druhý jen optimalizuje, takže se mu říká "zelený"

% Drobné okénko o negaci v Prologu:

% Takhle je definována negace.
% Je důležité si uvědomit, že negace v Prologu není důkaz negovaného X,
% ale spíše to, že Prolog nebyl schopen X dokázat.
not(X) :- X, !, fail.
not(X).
% Obvykle zapisováno jako prefixový unární operátor \+

% Mějme následující malou databázi:
clovek(adam).
clovek(eva).

muz(adam).
zena(eva).

% swipl> \+ muz(eva).
% true.

% swipl> \+ zena(eva).
% false.

% Začne to fungovat trochu pochybně u volných proměnných:
% swipl> \+ muz(X).
% false.

% Prolog nebyl schopen dokázat, že X není `muz`, tedy odpověděl `false`

% To co jsme asi chtěli napsat je:
% swipl> clovek(X), \+ muz(X).
% X = eva.

% Syrové řezy jsou trochu jako GOTO v imperativních jazycích.
% Samozřejmě je používat můžete, ale občas jsou i konkrétnější použití.
% (Podobně jako používáte `for` loop místo obecného `goto` v Céčku)

% \+ je negace
% \= je "neunifikovatelné s" -- definováno cca takhle: X \= Y :- \+ (X = Y).

% `once` se postará o to, aby se něco stalo nejvýše jednou.
once(P) :- P, !.

% `_ -> _ ; _` je if/else.
% Například `max` se asi nejlépe naprogramuje s ifem následovně:
maxIf(A, B, R) :-
    (A < B -> R = B; R = A).

2-sort.pl

% U této funkce jsme hádali co dělá.
rozdel([], _, _, [], []).
rozdel([H|T], Fn, Param, ResultYes, ResultNo) :-
    rozdel(T, Fn, Param, Yes, No),
    ( call(Fn, H, Param) ->                          % if Fn(H, Param)
        ResultYes = [H | Yes], ResultNo = No;        % then this
        ResultYes = Yes,       ResultNo = [H | No]   % else this
    ).
% Vezme seznam, funkci a parametr a volá pro každý prvek X: Fn(X, Param)
% Pokud tento cíl uspěje, pak X jde do seznamu `ResultYes`, pokud ne, tak jde do seznamu `ResultNo`.
% Všimněte si použití našeho `if`u a rozmyslete si co by se stalo bez řezu.
% (A tedy rozhodněte, je-li tento řez "červený", či "zelený".

% Typické použití vypadá následovně:
mensi(X, Y) :- X < Y.

% swipl> rozdel([1, 4, 3, 2, 5], mensi, 3, Mensi, VetsiRovno).
% Mensi = [1, 2]
% VetsiRovno = [4, 3, 5]

% Poměrně přirozeně můžeme tedy naprogramovat quicksort:
qsort([], []).
qsort([Pivot|L], Utridene) :-
    rozdel(L, mensi, Pivot, Mensi, Vetsi),
    qsort(Mensi, UtrideneMensi),
    qsort(Vetsi, UtrideneVetsi),
    append(UtrideneMensi, [Pivot|UtrideneVetsi], Utridene).
    
% Pozor, že poslední `append` určitě není O(1)!
% Tohle opravíme na příštím cvičení :)

3-hof.pl

% Minule jsme dělali funkci `mapa`, dneska jsme si udělali dvě verze:
% mapa/3 je stejná jako na předchozím cvičení -- na prvek X se pokusí splnit Fn(X, XResult) a XResult dá do nového seznamu.
% mapa/4 vezme ještě jeden parametr a pokouší se splnit Fn(X, Param, XResult)
mapa([], _, []).
mapa([H|T], Fn, [H2|T2]) :-
    call(Fn, H, H2),
    mapa(T, Fn, T2).

mapa([], _, _, []).
mapa([H|T], Fn, Param, [H2|T2]) :-
    call(Fn, H, Param, H2),
    mapa(T, Fn, Param, T2).
    
% Ještě si sem nakopírujeme `rozdel` z předchozího souboru:
rozdel([], _, _, [], []).
rozdel([H|T], Fn, Param, ResultYes, ResultNo) :-
    rozdel(T, Fn, Param, Yes, No),
    ( call(Fn, H, Param) ->                          % if Fn(H, Param)
        ResultYes = [H | Yes], ResultNo = No;        % then this
        ResultYes = Yes,       ResultNo = [H | No]   % else this
    ).

% Napíšeme si teď pomocí `rozdel` a `mapa` transpozici matice!

% Pomocné predikáty
hlava([H|_], H).
zbytek([_|T], T).
prazdny([], _).

% Splnitelný iff všechny seznamy v X jsou prázdné.
vsechny_prazdne(X) :-
  rozdel(X, prazdny, _, _, []). % můžeme použít rozděl a ověřit, že není nevyhovující prvek X (tedy `No = []`)

% Transpozice matice M je prázdný seznam pokud jsou všechny řádky prázdné.
trans(M, []) :-
  vsechny_prazdne(M).
  
% Teď samotná rekurze.
trans(M, [PrvniSloupec|TransSloupce]) :-
    
    % mapa(M, hlava) vybere prvky *_*
    %  [*1*, 2, 3]
    %  [*4*, 5, 6]
    %  [*7*, 8, 9]
    mapa(M, hlava, PrvniSloupec),
    
    
    % mapa(M, zbytek) vybere seznamy *_*
    %  [1| *[2, 3]*]
    %  [4| *[5, 6]*]
    %  [7| *[8, 9]*]
    mapa(M, zbytek, ZbyleSloupce),
    
    % zarekruzíme se na zbylé sloupce
    trans(ZbyleSloupce, TransSloupce).

% Dále chceme udělat násobení matic.
% `fold` je další přirozené použití for-loopu.
% V Pythonu odpovídá:
% ```python
% result = None
% for x in xs:
%   result = f(result, x)
% return result
% ```
% Konkrétně tedy funkce stylu: "sečti všechny prvky"/"vynásob všechny prvky"
% Občas se jí říká `reduce`, popř. `reduceLeft`.

% fold(@Fn, +Seznam, -Prvek)
% Seznam = [1, 2, 3, 4]
% idea: chceme `Fn(Fn(Fn(1, 2), 3), 4)`
% V hlavě `Seznam`u si budeme uchovávat akumulátor -- momentální hodnotu. 
fold(_, [], _) :- fail. % prázdný seznam je fuj
fold(_, [X], X).        % máme-li jen jeden prvek, vrátíme ho
fold(Fn, [A, B | T], Y) :- 
    call(Fn, A, B, Acc),     % zavoláme Fn(A, B, Acc) 
    fold(Fn, [Acc | T], Y).  % zarekurzíme se, hodíme Acc na začátek seznamu

% Pomocné funkce, které se nám budou hodit za chvilku :)
krat(X, Y, Z) :- Z is X * Y.
plus(X, Y, Z) :- Z is X + Y.

% Další taková funkce, která bere funkce je `zip`, která aplikuje funkci na prvky pod sebou,
% viz obrázek níže:
% zip(+Xs, +Ys, @Fn, -ResultList)
% Xs =          [1,        2,        3, ...]
% Ys =          [5,        6,        7, ...]
% ResultList =  [Fn(1, 5), Fn(2, 6), Fn(3, 7), ...]
zip([], [], _, []).
zip([H1|T1], [H2|T2], Fn, [H3|T3]) :-
    call(Fn, H1, H2, H3),
    zip(T1, T2, Fn, T3).

% Nyní můžeme rychle a hezky napsat násobení matic.

% Začněme skalárním součinem:
krat_vektor_vektor(V1, V2, R) :-
    zip(V1, V2, krat, X), % Vynásobíme prvky "pod sebou"
    fold(plus, X, R).     % Všechny je sečteme.

% Násobení vektoru maticí:
krat_vektor_matice(V, M, NV) :-
    % i-tý prvek výsledného vektoru je skalární součin i-tého řádku M a vektoru V
    mapa(M, krat_vektor_vektor, V, NV).

% Násobení matice maticí:
krat_matice_matice(X, Y, V) :-
    % Nejprve otočíme Y, abychom k ní mohli přistupovat "po sloupcích"
    trans(Y, TransY),
    
    % i-tý řádek výsledné matice je násobení i-tého řádku X s maticí Y.
    mapa(X, krat_vektor_matice, TransY, V).
    
% Funkcím, které berou funkce jako argumenty se říká "higher-order funkce"
% a jsou elegantním způsobem, jak se vyhnout explicitní rekurzi.
% Na explicitní rekurzi je často nahlíženo jako na zbytečně "low-level" věc,
% podobně opět jako GOTO z imperativních jazyků.
% S podobnými funkcemi si budeme hodně hrát později v Haskellu. :)