%
% Important note: the following class example is provided "as
% is", for reference purposes, and without any claims of correctness.
%

:- use_module(library(clpq)).

% 9.1

% 1
reverse(L, R) :- reverse(L, [], R).
reverse([], Acc, Acc).
reverse([H|T], Acc, R) :- reverse(T, [H|Acc], R).

% 2
last([E], E).
last([_|T], E) :- last(T, E).

% 3
remove_at([H|T], 1, H, T).
remove_at([H|T], N, X, [H|R]) :-
	Np is N - 1,
	remove_at(T, Np, X, R).

% 4
clpq_inject([]).
clpq_inject([H|T]) :- {H}, clpq_inject(T).

% 5
gcd(N, M, Gcd) :- N < M, gcd_euclid(M, N, Gcd).
gcd(M, N, Gcd) :- gcd_euclid(M, N, Gcd).
gcd_euclid(M, 0, M).
gcd_euclid(M, N, Gcd) :-
	Remainder is M mod N,
	gcd_euclid(N, Remainder, Gcd).

% 6
coprime(M, N) :- gcd(M, N, 1).

% 7
imp(A, B) :- { A }, entailed(B).

% 8
fib(N, _) :- N < 0, !, fail.
fib(0, 0).
fib(1, 1).
fib(N, F) :-
	Np is N - 1,
	Npp is N - 2,
	fib(Np, Fp),
	fib(Npp, Fpp),
	F is Fp + Fpp.

% 9
sum([], 0).
sum([H|T], S) :- sum(T, Sp), S is Sp + H.

% 10
consistent(L, F) :- clpq_inject(L), { F }.

% 11
tree(t(3,
       t(1,
	 t(0, e, e),
	 t(2, e, e)
	),
       t(7,
	 t(4, e, e),
	 t(10,
	   t(8, e, e),
	   e
	  )
	)
      )
    ).

binary_search(t(N, _, _), N).
binary_search(t(D, _, R), N) :- D < N, binary_search(R, N).
binary_search(t(D, L, _), N) :- N < D, binary_search(L, N).



% 9.3, see creach-more.pl

% 9.6, see mysmc-mod.pl

% 9.7, see fsr-mod.pl
