/* 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.

*/

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

%% 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) succeds 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) succeds 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) succeds 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).

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