-
-
Save jiribenes/0e22b10080245e889ba6ac7935c3461a to your computer and use it in GitHub Desktop.
Cvičení z Neprocedurálního programování - 4
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% 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). |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% 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í :) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% 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