/*
	Prolog list demos.
*/

/* member(X,L) -- X is a member of list L */
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).

/* prefix(P,L) -- P is a prefix of the list L */
prefix([],Ys).
prefix([X|Xs],[X|Ys]) :- prefix(Xs,Ys).

/* sublist(S,L) -- S is a sublist of the list L */
sublist(Xs,Ys) :- prefix(Xs,Ys).
sublist(Xs,[Y|Ys]) :- sublist(Xs,Ys).

/* member2(X,L) -- X is a member of list L implemented using sublist */
member2(X,Xs) :- sublist([X],Xs).

/* length(L,N) -- there are N elements in list L */
length([],0).
length([X|Xs],N) :- length(Xs,N1), N is N1+1.

/* length(L,N) -- there are N elements in list L (accumulator-style) */
length2(L,N) :- alength(L,0,N).
alength([],A,A).
alength([H|T],A,N) :- A1 is A+1, alength(T,A1,N).

/* append(L1,L2,L) -- L is the list formed by appending L2 to L1 
	1) take apart L1 ([X|Xs])
	2) the result (L) is [X|Zs]
	3) what is Zs? just L2 appended to Xs [Xs|Ys] */
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

/* reverse(L,R) -- R is the list L reversed 
   goal order is important!
	reverse([a,b,c], R) OK
	reverse(R,[a,b,c]) non-terminating! 
   what happens if you reverse the goal order? */
reverse([],[]).
reverse([X|Xs],Zs) :- reverse(Xs,Ys), append(Ys,[X],Zs).

/* range(M,N,L) -- L is an ordered list of numbers in the range [M..N] */
range(M,N,[M|Ns]) :- M<N, M1 is M+1, range(M1,N,Ns).
range(N,N,[N]).

/* sumlist(L,N) -- N is the sum of integers in list L
	uses "tail recursion"; essentially a form of iteration */
sumlist(Is,Sum) :- sumlist(Is,0,Sum).
sumlist([I|Is],Temp,Sum) :- Temp1 is Temp+I, sumlist(Is,Temp1,Sum).
sumlist([],Sum,Sum).

/* non_parent(P,C) -- P is not C's parent
	demonstrates problem with not() */
non_parent(X,Y) :- not(father(X,Y)), not(mother(X,Y)).

/* min(X,Y,M) -- M is the minimum of X and Y
	demonstrates "cut" */
min(X,Y,X) :- X=<Y, !.
min(X,Y,Y) :- X>Y, !.

/* not2(P) -- P can't be proven ("failure as negation")
   uses special primitives call, cut and fail */
not2(P) :- call(P), !, fail.
not2(P).