% examples of {P}NUE-Prolog
% ({Parallel}NU-Prolog with Equations)
%
% f(X) = Y. defines an equation
% g(X) == Y. is similar but it is compiled in-line
% (only one equation for g is allowed,
% - not currently checked though)
% h(X) = Y :- Body. defines a conditional equation
%
% (C ? A : B) is a built in function. It is equivalent
% to the following definition
% (C ? A : B) == X :- (if C then X = A else X = B).
% but doesn't evaluate both A and B
%
% To be run in parallel, the left sides of equations must
% not unify with the left sides of previous equations
% (at least those without cut in the body, which is not
% highly recommended).
% should be in some standard definition file
A + B == C :- C is quote(A + B). % could use plus/3
A - B == C :- C is quote(A - B). % maybe not ('-' is used lots)
A * B == C :- C is quote(A * B).
A // B == C :- C is quote(A // B).
univ_f(F) == L :- F =.. L.
univ_l(L) == F :- F =.. L.
% should do arg, functor, name etc also
% goals
:- writeln(fact1(7)).
% append
concat([], A) = A.
concat(A.B, C) = A.concat(B, C).
% append 3 lists together
append3(A, B, C) = concat(A, concat(B, C)).
%append3(A, B, C) = concat(concat(A, B), C). % less efficient
% reversible version - like outermost evaluation
% of first definition
%append3(A, B, C, D) :- concat(A, X, D), concat(B, C, X).
% sum integers in a tree
sum_tree(nil) = 0.
sum_tree(t(L, N, R)) = sum_tree(L) + N + sum_tree(R).
% flatten tree into list
flatten_tree(nil) = [].
flatten_tree(t(nil, N, R)) = N.flatten_tree(R).
flatten_tree(t(t(LL, LN, LR), N, R)) =
flatten_tree(t(LL, LN, t(LR, N, R))).
% sum integers in a list
sum([]) = 0.
sum(A.B) = A + sum(B).
% max of two numbers
nmax(A, B) = (A >= B ? A : B).
% max of list of numbers (efficient tail recursive version)
max_l(A.B) = max_l1(A, B).
max_l1(A, []) = A.
max_l1(A, B.C) = max_l1(nmax(A, B), C).
% add two lists of numbers, pairwise
% illustrates uniform defn
add_lists([], _) = [].
add_lists(_._, []) = [].
add_lists(A.As, B.Bs) = (A+B).add_lists(As, Bs).
% insertion sort (inefficient version)
isort([]) = [].
isort(A.B) = insert(A, isort(B)).
insert(A, []) = [A].
insert(A, B.C) = (A =< B ? A.B.C : B.insert(A, C)).
% insertion sort (more efficient version)
isort1(L) = isort1a(L, []).
% insertion sort with accumulator
isort1a([], Ac) = Ac.
isort1a(H.T, Ac) = isort1a(T, insert(H, Ac)).
% factorial
% should use ?: to get mutex heads (or cut - yuk)
% This definition results in an error message
fact(0) = 1.
fact(N) = N * fact(N - 1) :- N > 0.
% like this!
fact1(N) = (N > 0 ? N * fact1(N - 1) : 1).
% 91 function
f91(X) = (X > 100 ? X - 10 : f91(f91(X + 11))).
% quicksort (inefficient version, without difference lists)
% shows limitation of functional notation
% - part has two outputs
qs([]) = [].
qs(A.B) = concat(qs(L), A.qs(G)) :- part(A, B, L, G).
% needs cuts or if for PNU-Prolog
part(A, [], [], []).
part(A, B.C, B.D, E) :- B =< A, part(A, C, D, E).
part(A, B.C, D, B.E) :- B > A, part(A, C, D, E).
% test if max element of list is greater than another list
% (only decent example of calling functions from Prolog
% I could think of)
gt_l(A, B) :- max_l(A) > max_l(B).
% zip2 as in Miranda
zip2([], _) = [].
zip2(_._, []) = [].
zip2(A.As, B.Bs) = (A, B).zip2(As, Bs).
% appends single element onto list
insertlast(E, []) = [E].
insertlast(E, H.T) = H.insertlast(E, T).
% should put in more Prolog examples, with
% function calls in the body