%  =================================================================
%  ==                                                             ==
%  ==          An Introduction to ARTIFICIAL INTELLIGENCE         ==
%  ==                  Janet Finlay and Alan Dix                  ==
%  ==                       UCL Press, 1996                       ==
%  ==                                                             ==
%  =================================================================
%  ==                                                             ==
%  ==             list and set processing predicates              ==
%  ==                                                             ==
%  ==            Prolog example, Alan Dix, August 1996            ==
%  ==                                                             ==
%  =================================================================

% concat/3, length/2, element_at/3
% member/2, count_members/3, add_member/3
% remove_member/3, remove_members/3, remove_list/3
% notsubset/2, subset/2, sameset/2
% union/3, intersect/3, setdiff/3
% sumlist/2, maxlist/2
% range_list/3

concat([],L,L).
concat([X|A],B,[X|L]) :- concat(A,B,L).

%  length/2 has a base case and two inductive cases
%  This is because there are two polymorphic cases.
%  One case is where the length is given and the predicate builds
%  a list of the given length,
%  The other is where the list is given and the length is being calculated.
length([],0).
length([X|L],N1) :-        %  this case when the length is given
        nonvar(N1), !,
        N1 > 0,
        N is N1 - 1,
        length(L,N).
length([X|L],N1) :-        %  this case to determine the length
        length(L,N),
        N1 is N + 1.

%  element_at/3 similarly has to cover different ploymorphic cases
%  element_at1(L,N,X) deals with the case when N is fixed when it
%  unifies the corresponding element of L with X
%  element_at2(L,N,X) deals with the case when N is unknown and
%  finds all those locations where X matches the Nth element of L
element_at(L,N,X) :-
            nonvar(N), !,
            element_at1(L,N,X).
element_at(L,N,X) :-
            element_at2(L,N,X).

element_at1([],N,X) :- !, fail.
element_at1([X|L],1,X) :- !.
element_at1([X|L],N,Y) :-
            N > 1,
            N1 is N-1,
            element_at1(L,N1,Y).

element_at2([],N,X) :- !, fail.
element_at2([X|L],1,X).
element_at2([X|L],N,Y) :-
            element_at2(L,N1,Y),
            N is N1 + 1.

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

%  member(X,[Y|L]) :-                 % looks right, but doesn't work
%              not Y=X, member(X,L).  % polymorphically to enumerate list

%  count_members(X,S,N) counts how many menmbers of S match X
%  and returns the count in N
%  it does not attempt to work polymorphically, but X need not be ground

count_members(X,[],0).
count_members(X,[X|L],N1) :-
        count_members(X,L,N),
        N1 is N + 1.
count_members(X,[Y|L],N) :-
        not Y=X,
        count_members(X,L,N).

add_member(X,S,S) :-
        member(X,S), !.     %  don't add duplicate members
add_member(X,S,[X|S]).

remove_member(X,[],[]).
remove_member(X,[X|L],L).
remove_member(X,[Y|L],[Y|Res]) :-
                not Y=X, remove_member(X,L,Res).
%  N.B. only works for ground X

remove_members(X,[],[]).
remove_members(X,[X|L],Res) :- !, remove_members(X,L,Res).
remove_members(X,[Y|L],[Y|Res]) :-
                remove_members(X,L,Res).

remove_list([],L,L).
remove_list([X|Rest],Lold,Lnew) :-
        remove_member(X,Lold,Lx),
        remove_list(Rest,Lx,Lnew).


notsubset(S1,S2) :- member(X,S1), not member(X,S2).

subset(S1,S2) :- not notsubset(S1,S2).

sameset(S1,S2) :- subset(S1,S2), subset(S2,S1).

union([],S,S).
union([X|S1],S2,S) :-
            member(X,S2), union(S1,S2,S).
union([X|S1],S2,[X|S]) :-
            not member(X,S2), union(S1,S2,S).

intersect([],_,[]).
intersect([X|S1],S2,[X|S]) :-
            member(X,S2), intersect(S1,S2,S).
intersect([X|S1],S2,S) :-
            not member(X,S2), intersect(S1,S2,S).

setdiff([],_,[]).
setdiff([X|S1],S2,S) :-
            member(X,S2), setdiff(S1,S2,S).
setdiff([X|S1],S2,[X|S]) :-
            not member(X,S2), setdiff(S1,S2,S).


sumlist(L,Sum) :- sumlist2(L,0,Sum).

sumlist2([],Sum,Sum).
sumlist2([N|L],S1,Sum) :-
            S2 is S1 + N,
            sumlist2(L,S2,Sum).


maxlist([N|L],Max) :- maxlist2(L,N,Max).

maxlist2([],Max,Max).
maxlist2([N|L],M1,Max) :-
            domax(N,M1,M2),
            maxlist2(L,M2,Max).

domax(N,M,N) :- N > M, !.
domax(N,M,M) :- N =< M.


range_list(Lo,Hi,[]) :-
            Lo > Hi, !.
range_list(Lo,Hi,[Lo|Rest]) :-
            Lo1 is Lo + 1,
            range_list(Lo1,Hi,Rest).

%  RUNNING THIS CODE
%