% t2 -- higher level functions, olvashato exampe code
% Zsban Ambrus

% mod(+X, +Y, -Mod):
% Mod is the remainder of Y divided by X.
mod(X, Y, Mod) :- 
    Mod is X - (Y * (X // Y)).

% loop(+Func, +Init, -Loop):
% Repeatedly calls the one-argument function object Func.  If it
% returns a next(X) object, the function will be called with X
% as argument the next time.  If it returns a last(Y) object, the
% iteration stops, and Loop is Y.
loop(Func, Init, Loop) :- 
    Fun = fun(Wrfunc, Pstate, Let, 
    (copy_term(Func, fun(Pstate, Call, Body)), Body, 
    (next(Nstate) = Call -> loop_helperfunc(Rfunc) = Wrfunc, 
    copy_term(Rfunc, fun(Wrfunc, Nstate, Let, Body1)), 
    Body1; 
    last(R) = Call, Let = R))), 
    Lfunc = Fun, 
    Loop_helperfunc = loop_helperfunc(Lfunc), 
    Wlfunc = Loop_helperfunc, 
    copy_term(Lfunc, fun(Wlfunc, Init, Loop, Body2)), 
    Body2.

% iota(+N, -Iota):
% Iota is the list of numbers from 0 to N - 1.
iota(N, Iota) :- 
    loop(fun(S, Case, (rec(K, D) = S, 
    (K =< 0 -> Case = last(D); Diff is K - 1, Diff1 is K - 1, 
    Case = next(rec(Diff, [Diff1| D]))))), 
    rec(N, []), 
    Iota).

% all(+Func, +List, -All):
% Calls the one-argument boolean function Func for each element
% of the list List while the function keeps returning tru.
% All is fals if the function ever returned fals; tru if
% we've reached the end of the list.
all(Func, List, All) :- 
    loop(fun(L, Case, (([] = L -> Case = last(tru); [A| D] = L, 
    (copy_term(Func, fun(A, Call, Body)), Body, tru = Call -> 
    Case = next(D); Case = last(fals))))), 
    List, 
    All).

% cdr(+L, -Cdr):
% Cdr is the cdr of a list.
cdr(L, Cdr) :- 
    [A| D] = L, !, Cdr = D.
cdr(L, Cdr) :- 
    X = L, abort, Cdr = rec.

% prime_(+N, -Prime_):
% Prime_ is tru iff N is a prime number.  N must be at least 2.
prime_(N, Prime_) :- 
    iota(N, Iota), cdr(Iota, Cdr), cdr(Cdr, Cdr1), 
    all(fun(D, Cond, 
    ((mod(N, D, Mod), 0 =\= Mod -> Cond = tru; Cond = fals))), 
    Cdr1, 
    Prime_).

% rev(+L, -Rev):
% Rev is a list contaning the elements of the list L in reverse
% order.
rev(L, Rev) :- 
    loop(fun(S, Case, 
    ((rec([A| D], R) = S -> Case = next(rec(D, [A| R])); 
    rec([], R1) = S, Case = last(R1)))), 
    rec(L, []), 
    Rev).

% filter(+Func, +List, -Filter):
% Calls the one-argument boolean function Func for each element of
% the list List.  Filter is the list of those elements in List for
% which the function returned true.
filter(Func, List, Filter) :- 
    loop(fun(S, Case, ((rec([A| D], R) = S -> 
    (copy_term(Func, fun(A, Call, Body)), Body, tru = Call -> 
    Cond = [A| R]; Cond = R), Case = next(rec(D, Cond)); 
    rec([], R1) = S, Case = last(R1)))), 
    rec(List, []), 
    Loop), 
    rev(Loop, Filter).

% list_primes(+N, -List_primes):
% List_primes is the list of primes less than or equal to N in 
% increasing order.
list_primes(N, List_primes) :- 
    iota(N, Iota), cdr(Iota, Cdr), cdr(Cdr, Cdr1), filter(
    fun(K, Prime_, (prime_(K, Prime_))), Cdr1, List_primes).

