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

0-warmup.prolog

%% Procvičení na začátek

% a) Napište predikát `same_as(?List, ?Elem)`,
% který je splněn, pokud každý prvek v `List` je `Elem`.
% Použijte `maplist/2`.

% b) Napište predikát `same(?List)`,
% který je splněn, pokud je každý prvek v `List` stejný
% (tj. roven _nějakému_ prvku).
% Použijte `same_as/2` definovaný výše, či rovnou `maplist/2`

%% Verze bez `maplist/2`
same_as([], _).
same_as([Elem | Tail], Elem) :-  % implicitně unifikujeme `Head = Elem`
  same_as(Tail, Elem).
  
same(List) :- same_as(List, _). 
% `_` značí novou, v tomto případě existenční, proměnnou
% Tohle bude fungovat, protože nám stačí, že `Elem` _existuje_.
% Zkuste si ve swiplu vy-trace-ovat `same`. :)

%% Verze s `maplist/2`
better_same_as(List, Elem) :-
  maplist(=(Elem), List).   % pro každý prvek `X` musí platit, že `Elem = X`! :)
% => Tedy `maplist/2` se chová jako "all" ... pokusí se splnit zadaný predikát pro každý prvek

better_same(List) :-
  maplist(=(_), List). % Viz výše, opět nás nezajímá _jaký_ prvek má být stejný, stačí že takový existuje.



%% Pokračování -- tohle zkuste samostatně:

% c) Vyrobte predikát `rectangle(?Matrix)`, který dostane seznam seznamů reprezentující matici
% a uspěje, pokud je zadaná matice obdélníková.
% Použijte `maplist/3` (`mapa` z minulého cvičení!) a `same/2` (napsané výše),
% Nápověda: matice je obdélníková, pokud délky všech řádků jsou stejné ;)

1-rezy.prolog

% 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 zhruba 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 _něco jako_ if/else, jen při tom řeže.
% Například `max` se asi nejlépe naprogramuje s ifem následovně:
maxIf(A, B, R) :-
    ( A < B
   -> R = B
    ; R = A).
    
% Varování: typicky nechcete používat `_ -> _ ; _`, může se to chovat trochu neintuitivně
% pokud chcete vícero výsledků. Pokud jen chcete `if`, tak si rozmyslete jak jsme programovali doteď
% [prostě stačí splňování podmínek a unifikace, ne? :)]

2-qsort.prolog

% 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)
   -> ResultYes = [H | Yes], ResultNo =      No
    ; ResultYes =      Yes , ResultNo = [H | No]
    ).

% 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 tohoto řezu.
% (A tedy rozhodněte, je-li tento řez "červený", či "zelený".)

% Typické použití vypadá následovně:
%
% swipl> rozdel([1, 4, 3, 2, 5], <, 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, <, 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.prolog

% Nakopírujeme `rozdel` z minulého souboru :)
rozdel([], _, _, [], []).
rozdel([H | T], Fn, Param, ResultYes, ResultNo) :-
    rozdel(T, Fn, Param, Yes, No),
    ( call(Fn, H, Param)
   -> ResultYes = [H | Yes], ResultNo =      No
    ; ResultYes =      Yes , ResultNo = [H | No]
    ).

% Minule jsme dělali funkci `mapa` -- ve std. knihovně najdete jako `maplist/3`.
% Napíšeme si teď pomocí `rozdel` a `maplist` 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]
    maplist(hlava, M, PrvniSloupec),
    
    
    % mapa(M, zbytek) vybere seznamy *_*
    %  [1| *[2, 3]*]
    %  [4| *[5, 6]*]
    %  [7| *[8, 9]*]
    mapa(zbytek, M, ZbyleSloupce),
    
    % zarekruzíme se na zbylé sloupce
    trans(ZbyleSloupce, TransSloupce).
    
% 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.

% 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

% Vyzkoušejte `fold(plus, [1, 2, 3, 4], X)` a `fold(krat, [1, 2, 3, 4], X)` ve swiplu.


% 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).
% V Prologové standardní knihovně existuje jako `maplist/4` (pozor na přehozené argumenty!)
% Této funkci se také občas říká `zipWith` ve funkcionální terminologii :)

%%%% Přehled různých `maplistů`:
% | maplist/2  | jeden vstup, žádný výstup | každý prvek seznamu musí splnit zadaný predikát                     |
% | maplist/3  | jeden vstup, jeden výstup | každý prvek je změněn dle predikátu                                 |
% | maplist/4  | dva vstupy, jeden výstup  | i-tý prvek výstupu je predikát aplikovaný na i-tý prvek obou vstupů |

%%%% Zpátky k násobení matic:

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

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

% Násobení matice maticí:
krat_matice_matice(A, B, C) :-
    % Nejprve otočíme B, abychom k ní mohli přistupovat "po sloupcích"
    trans(B, TransB),
    
    % i-tý řádek výsledné matice je násobení i-tého řádku X s maticí Y.
    maplist(krat_matice_vektor(A), TransB, C).
    
% 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. :)