Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Last active March 18, 2021 10:19
Show Gist options
  • Save jiribenes/eb5428019bae7439d69e1bc1f7a0d0c9 to your computer and use it in GitHub Desktop.
Save jiribenes/eb5428019bae7439d69e1bc1f7a0d0c9 to your computer and use it in GitHub Desktop.
Cvičení z Neproceduráního programování - 3
% V předchozím díle jste viděli:
% Otočí spojový seznam
% Tahle funkce je technicky O(N^2), jde to i lineárně, jak uvidíme příště. :)
% 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, Result, NewResult), % NewResult = Head + Result
soucet(Tail, NewResult).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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).
% 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
% 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).
% Tyto funkce byly jako hádanky:
foo([], [], []).
foo([A], [A], []).
foo([A, B|R], [A|L], [B|P]) :-
foo(R, L, P).
bar([], []).
bar([_|A], [_|B]) :- bar(A, B).
% Spoiler: `foo` rozdělí seznam na prvky se sudými a lichými členy.
% Spoiler: `bar` zkontroluje, že dva seznamy mají stejný počet prvků.
%%%%%%%%%%%
% Najdi prostředek seznamu (bez aritmetiky!)
prostredek(S, X) :- prostredek_(S, S, X).
% prostredek_:
% - První argument skáče po dvou
% - Druhý argument skáče po jednom
% - Pokud se první argument dostal na konec, pak druhý je v půlce!
prostredek_([], [X|_], X).
prostredek_([_], [X|_], X).
prostredek_([_,_|Xs], [_|Ys], Result) :-
prostredek_(Xs, Ys, Result).
% 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).
% 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment