/* Some examples of recursion.
 *
 *   member(X,List)  succeeds if X is a member of List
 *   append(L1,L2,Ans)  succeeds if Ans is the concatenation of
 *                      L1 and L2
 *   get_n(L,Ans,N)  succeeds if Ans is the list containing the
 *                   first N elements of L
*/

member(X,[X|L]).
member(X,[_|L]) :- member(X,L).

append([X|L3],L4,[X|Ans1]) :- append(L3,L4,Ans1).
append([],L,L).

get_n([],[],_).
get_n([X|L1],[X|Ans1],N) :-
         N>0,
         N1 is N-1,
         get_n(L1,Ans1,N1).
get_n(_,[],0).

/* A more elaborate example: the highest common factor of
 * two numbers, using a simplistic version of Euclid's algorithm, viz.
 * h.c.f. of M and N = h.c.f. of min(M,N) and M-N
 * NOTE: the clauses given below ASSUME you're going to
 *       call hcf(M,N,Ans) with M>0, N>0, M>N. If you
 *       want to avoid this assumption, you should have
 *       a top-level predicate hcf1 (say), defined
 *
 *       hcf1(M,N,Ans) :- tidy(M,N,Mnew,Nnew), hcf(Mnew,Nnew,Ans).
 *
 *       where 'tidy' cleans up M and N. This is more
 *       efficient than just having another clause for hcf,
 *       since if you study the clauses below, you'll find
 *       that once the conditions are met, subsequent hcf goals
 *       also meet them.
 * ALSO: note the use of the cuts to express "if you've got here,
 *       you've found the answer - no need to backtrack".
 */

hcf(M,N,Ans) :-
         M=N,
         Ans is N,
         !.
hcf(M,N,Ans) :-
         Z is M-N,
         0 is N mod Z,
         Ans is Z,
         !.
hcf(M,N,Ans) :-
         Z is M-N,
         Z<N,
         hcf(N,Z,Ans).
hcf(M,N,Ans) :-
         Z is M-N,
         hcf(Z,N,Ans).

/* This is a neater version, using a more sensible form
 * of Euclid's algorithm, viz.
 *  h.c.f. of M and N = h.c.f. of m and (N mod M).
 * If N>M, then max(N,M) > max(M,(N mod M)), so if
 * you keep repeating this, the maximum steadily
 * decreases. Therefore it must be zero at some point,
 * and you know h.c.f. of 0 and X is just X.
 *
 * Subtle point (?): IF N =< M, then
 *  max(N,M) >= max(M,(N mod M)), so even in this
 * case the maximum doesn't increase - though it may
 * stay the same. THEREFORE, if we arrange to swap the
 * arguments round at every step, the max must decrease
 * at every other step!
 *
 * To avoid confusion, the predicate will be mcd in this
 * version (= maximum common divisor).
 * Again, note the use of the 'cut'.
 *
 * Compare hcf and mcd for speed! If you try
 * hcf(10000,10,X), you'll have to wait a bit...
 */

mcd(N,0,N) :- !.
mcd(N,M,D) :- R is N mod M, mcd(M,R,D).