/*  LISTS.PL  */


/*
:- module lists.

:- public append/3,
          append_n/2,
          islist/1,
          last/2,
          length/2,
          member/2,
          member/3,
          reverse/2,
          rev_append/3,
          nth1/3,
          nth1/4,
          delete/3,
          sublist/3,
          sublist0/2,
          sublist1/2.
*/


/*
SPECIFICATION
-------------

This module defines some common list predicates, giving them their usual
(?) definitions.


PUBLIC append( L1?, L2?, L3? ):

L3 is the result of appending L2 to L1.


PUBLIC append_n( Lists+, Result ):

Result is the result of appending all elements of Lists together.



PUBLIC rev_append( R+, L+, Result- ):

Result is the result of reversing R and prepending it to L.



PUBLIC islist( L+ ):

L is the null list or something of the form [_|_]. This predicate does
not run all the way down L, checking each element.


PUBLIC last(Last?, List?):

Is true when List is a List and Last is its last element.


PUBLIC length( L?, N? ):

N is the length of list L.


PUBLIC member( Element?, L? ):

Element is a member of L.


PUBLIC member( Element?, L?, Rest? ):

Element is a member of L. Rest is the rest of L.


PUBLIC reverse( L1?, L2? ):

L2 is the result of reversing L1.


PUBLIC nth1( N+, List+, Elem? ):

This is true when Elem is the Nth member of List, counting the first as
element 1. (That is, throw away the first N-1 elements and unify Elem with
the next.) It can only be used to select a particular element given the
list and index.


PUBLIC nth1( N+, List+, Elem?, Rest? ):

This is true when Elem is the Nth member of List, counting the first as
element 1, and Rest is the rest of the list. It can only be used to
select a particular element given the list and index.


PUBLIC delete( List+, Element+, List1- ):

Deletes all matches of Element from List, producing List1.

Free variables in Element are not bound after the first deletion, so
    delete( L, (_,X), L1 )
(where X is bound) will delete all pairs (_,X) from L.


PUBLIC sublist( Sequence?, SubSequence?, Complement? ):

Is true when SubList and Complement are both subsequences of the list
List (the order of corresponding elements being preserved) and every
element of List which is not in SubList is in the Complement and vice
versa. That is,
    length(List) = length(SubList)+length(Complement), e.g.
    sublist([1,2,3,4], [1,3,4], [2]).
This was written to generate subsets and their complements together, but
can also be used to interleave two lists in all possible ways. Note that
if S1 is a subset of S2, it will be generated *before S2 as a SubList
and *after it as a Complement.

N.B. Beware of the order of arguments! I took this version from the
Dec-10 library; I'm sure I've seen versions with the sublist argument
_first_.


PUBLIC sublist0( List+, SubList? ):

Is true when SubList is a subsequence of List, but may be List itself.
Thus sublist0([a,b], [a,b]) is true as well as sublist0([a,b], [a]).


PUBLIC sublist1( List+, SubList? ):

Is true when SubList is a proper subsequence of List, that is it
contains at least one element less. Thus (assuming you have setof and
bagof):
    ?- setof(X, sublist0([a,b,c],X), Xs).
    Xs = [[],[a],[a,b],[a,b,c],[a,c],[b],[b,c],[c]]

    ?- bagof(X, sublist0([a,b,c,d],X), Xs).
    Xs = [[a,b,c,d],[b,c,d],[c,d],[d],[],[c],[b,d],[b],[b,c],[a,c,d],
    [a,d],[a],[a,c],[a,b,d],[a,b],[a,b,c]]
*/


/*
IMPLEMENTATION
--------------

As usual, reverse and length use accumulator arguments to make
tail-recursion optimisation possible.

On Poplog, length is already defined, so I've commented out the
definition below. Uncomment it if your system lacks it.

The obvious definition of 'last' would be
    last(Last, [Last]) :- !.
    last(Last, [_|List]) :-
        last(Last, List).

However (see "The Craft of Prolog" section 6.5.4), Prologs with indexing
execute that less efficiently than they ought, because the indexing
can't distinguish between [_] and [_|_]. I have therefore used O'Keefe's
definition. It runs faster on Poplog too, though for different reasons,
since Poplog does not index the arguments for last_1. As Steve Knight
pointed out to me, in Poplog, you can examine the code for each by
setting pop_show_code to true and then loading.

nth1 and subseq are taken from the DEC-10 library.
*/


append([], L, L).
append([H|R], S, [H|T]) :-
    append(R, S, T).


append_n( Lists, Result ) :-
    append_n( Lists, [], Result ).


append_n( [], Result, Result ) :- !.
append_n( [H|T], SoFar, Result ) :-
    append_n( T, SoFar, SoFar1 ),
    append( H, SoFar1, Result ).


islist([]) :- !.
islist([_|_]).


last( Last, [H|T] ) :-
    last_1( T, H, Last ).

last_1( [], Last, Last ) :- !.
last_1( [H|T], _, Last ) :-
    last_1( T, H, Last ).


/*
length( L, N ) :-
    length( L, 0, N ).

length( [], N, N  ) :- !.
length( [H|T], N0, N ) :-
    N1 is N0 + 1,
    length( T, N1, N ).
 */


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


member(X, [X|T], T).
member(X, [H|Y], [H|Rest]) :-
    member(X, Y, Rest).


reverse( X, RX ) :-
    reverse( X, [], RX ).

reverse( [], R, R ) :- !.
reverse( [X|Y], Z, R ) :-
    reverse( Y, [X|Z], R ).


rev_append( A, B, C ) :-
    reverse( A, B, C ).


nth1(1, [Head|_], Head) :- !.

nth1(N, [_|Tail], Elem) :-
    M is N-1,
    nth1(M, Tail, Elem).


nth1(1, [Head|Tail], Head, Tail) :- !.

nth1(N, [Head|Tail], Elem, [Head|Rest]) :-
    M is N-1,
    nth1(M, Tail, Elem, Rest).


delete( [], _, [] ) :- !.

delete( [H1|T], H2, L ) :-
    not(not(H1=H2)),
    /*  This stops H2's variables getting bound.  */
    !,
    delete( T, H2, L ).

delete( [X|T], H, [X|L] ) :-
    delete( T, H, L ).


sublist([], [], []).

sublist([Head|Tail], Sbsq, [Head|Cmpl]) :-
    sublist(Tail, Sbsq, Cmpl).

sublist([Head|Tail], [Head|Sbsq], Cmpl) :-
    sublist(Tail, Sbsq, Cmpl).


sublist0(List, List).

sublist0(List, Rest) :-
    sublist1(List, Rest).


sublist1([_|Tail], Rest) :-
    sublist0(Tail, Rest).

sublist1([Head|Tail], [Head|Rest]) :-
    sublist1(Tail, Rest).


/*
:- endmodule.
*/