/* PREDICATES ON LISTS

Many predicates in the following are redefinitions of built-in
predicates. In those cases, we will add "1" as a suffix to the name.

NOTE: the '%' character denotes a single line comment.

*/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% member(X,L) succeeds if X is member of list L.

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


/***** Example runs:

| ?- member1(b,[a,b,c]).        

true ? ;

no
| ?- member1(d,[a,b,c]).

no
| ?- member1(X,[]).     

no

| ?- member1(X,[a,b,c]).

XX = a ? ;

X = b ? ;

X = c ? ;

(1 ms) no

| ?- member1(a,L).      

L = [a|_] ? ;

L = [_,a|_] ? ;

L = [_,_,a|_] ? ;

L = [_,_,_,a|_] ? 

yes

| ?- member1(X,L).

L = [X|_] ? ;

L = [_,X|_] ? ;

L = [_,_,X|_] ? ;

L = [_,_,_,X|_] ? 


****/

 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% listlen(L,N) succeeds if L is a list and N is its length.

%% (Is built-in predicate in gprolog under the name length/2.)

listlen([],0).
listlen([H|T],N) :- listlen(T,N1), N is N1 + 1.

/***** Example runs:

| ?- listlen([a,b,c],3).

yes
| ?- listlen([a,b,c],4).

no
| ?- listlen([a,b,c],X).

X = 3

yes
| ?- listlen([],X).     

X = 0

yes
| ?- listlen(L,3). 

L = [_,_,_] ? ;

... infinite loop

*****/


%% A variant using an accumulator:

listlen2(L,N) :- lenacc(L,0,N).

lenacc([],A,A).
lenacc([H|T],A,N) :- A1 is A + 1, lenacc(T,A1, N).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% last(X,L) succeeds if X is last element of list L.

last1(X,[X]).
last1(X,[_|Y]) :- last1(X,Y).

/***** Example run:

| ?- last1(4,[2,3,4]).

true ? ;

no
| ?- last1(3,[2,3,4]).

no
| ?- last1(X,[2,3,4]).

X = 4 ? ;

no

*****/


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% nextto(X,Y,L) succeeds if X and Y are adjacent in list L.

nextto(X,Y,[X,Y|_]).
nextto(X,Y,[_|Z]) :- nextto(X,Y,Z).

%% First line could also have been 
%%   nextto(X,Y,[X,Y|_]) :- !.
%% but then we could not generate several solutions to 
%% e.g. nextto(X,Y,[2,3,4]).

/***** Example run:

| ?- nextto(2,3,[1,2,3,4]).

true ? ;

no
| ?- nextto(2,3,[1,2,3,4]).

true ? 

yes
| ?- nextto(2,4,[1,2,3,4]).

no
| ?- nextto(2,X,[1,2,3,4]).

X = 3 ? ;

no

| ?- nextto(2,X,[1,2,2,4]).

X = 2 ? ;

X = 4 ? ;

no

| ?- nextto(X,Y,[1,2,3,4]).

X = 1
Y = 2 ? ;

X = 2
Y = 3 ? ;

X = 3
Y = 4 ? ;

no

*****/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% append1(L1,L2,L3) succeeds if L3 is the concatenation of L1 and L2.

append1([],L,L).
append1([X|L1],L2,[X|L3]) :- append1(L1,L2,L3).

/***** Example run

| ?- append1([1,2],[4,5],Z).   

Z = [1,2,4,5]

yes
{1}
| ?- append1([1,2],Y,[1,2,3,4]).

Y = [3,4]

yes
{1}
| ?- append1([1,3],Y,[1,2,3,4]).

no
{1}
| ?- append1(X,Y,[1,2,3,4]).    

X = []
Y = [1,2,3,4] ? ;

X = [1]
Y = [2,3,4] ? ;

X = [1,2]
Y = [3,4] ? ;

X = [1,2,3]
Y = [4] ? ;

X = [1,2,3,4]
Y = [] ? 

(10 ms) yes
{1}
| ?- append1(X,[1,2,3,4],Z).    

X = []
Z = [1,2,3,4] ? ;

X = [A]
Z = [A,1,2,3,4] ? ;

X = [A,B]
Z = [A,B,1,2,3,4] ? ;

X = [A,B,C]
Z = [A,B,C,1,2,3,4] ? ;

X = [A,B,C,D]
Z = [A,B,C,D,1,2,3,4] ? 

yes

*****/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% rev(L1,L2) succeeds if L2 is the reverse list of L1. Built-in 
%% predicate is reverse.

rev([],[]).
rev([H|T],L) :- rev(T,Z), append(Z,[H], L).

%% rev2 is similar, but uses an ACCUMULATOR (more efficient: O(n) 
%% as opposed to O(n^2)).

%% revzap(RestL1,A,L3) succeeds if reverse(RestL1)+A = L3

%% (Idea of accumulator solution: 
%%  invariant is reverse(RestL1)+A = reverse(L1)).

rev2(L1,L2) :- revzap(L1,[],L2).
revzap([X|L], L2, L3) :- revzap(L,[X|L2],L3).
revzap([],L,L).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% efface(A,L1,L2) succeeds if L2 is L1 with first occurence (if any)
%% of A removed. 

%%% Somewhat similar predicate "select" exists in gprolog 

efface(_,[],[]).
efface(A,[A|L],L) :- !.
efface(A,[B|L],[B|M]) :- efface(A,L,M).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% delete1(A,L1,L2) succeeds if L2 is L1 with all occurences (if any)
%% of A removed. 

%%% Similar predicate exists "delete" in gprolog, but with two first
%%% arguments interchanged

delete1(_,[],[]).
delete1(X,[X|L],M) :- !, delete1(X,L,M).
delete1(X,[Y|L1],[Y|L2]) :- delete1(X,L1,L2).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% sublist1(L1,L2) succeeds if L1 is a consecutive segment of L2.

%% NOTE: the built-in gprolog predicate sublist(L1,L2) succeed if L1 is a
%% subsequence of L2 (i.e. not necessarily consecutive elements of L2).

%% The predicate prefix exists with the same meaning as here.

%% NB: The version in the book (page 158) has a cut, which is unnecessary
%% (and limiting in use of predicate). Also, first two lines are added, and
%% are necessary if the empty list should be a sublist.

sublist1([],M).
sublist1(L,M) :- sublist2(L,M).
%%Wrong:
%%sublist2([X|L],[X|M]) :- prefix(L,M),!.
sublist2([X|L],[X|M]) :- prefix(L,M).
sublist2(L,[_|M]) :- sublist2(L,M).

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% More list predicates, see Section 7.5 (and gprolog documentation)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%