Skip to content

Instantly share code, notes, and snippets.

@jiribenes

jiribenes/1-rezy.pl Secret

Last active Mar 26, 2021
Embed
What would you like to do?
Cvičení z Neprocedurálního programování - 4
% 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).
% 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í :)
% 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. :)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment