%   Package: basics
%   Author : by now, nobody knows
%   Updated: 7/29/85
%   Defines: the basic list processing predicates

:- public
	append/3,
	member/2,
	memberchk/2,
	nonmember/2.

:- mode
	append(?, ?, ?),
	member(?, ?),
	memberchk(+, +),
	nonmember(+, +).


%   append(?Prefix, ?Suffix, ?Combined)
%   is true when all three arguments are lists, and the members of Combined
%   are the members of Prefix followed by the members of Suffix.  It may be
%   used to form Combined from a given Prefix and Suffix, or to take a given
%   Combined apart.  For example, we could define member/2 as
%	member(X, L) :- append(_, [X|_], L).

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



%   member(?Element, ?Set)
%   is true when Set is a list, and Element occurs in it.  It may be used
%   to test for an element or to enumerate all the elements by backtracking.
%   Indeed, it may be used to generate the Set!

member(Element, [Element|_]).
member(Element, [_|Rest]) :-
	member(Element, Rest).



%   memberchk(+Element, +Set)
%   means the same thing, but may only be used to test whether a known
%   Element occurs in a known Set.  In return for this limited use, it
%   is more efficient than member/2 when it is applicable.

memberchk(Element, [Element|_]) :- !.
memberchk(Element, [_|Rest]) :-
	memberchk(Element, Rest).



%   nonmember(+Element, +Set)
%   means that Element does not occur in Set.  It does not make sense
%   to instantiate Element in any way, as there are infinitely many
%   terms which do not occur in any given set.  That being the case,
%   it is ok to use \= .  If we had a sound ~= we could use it here
%   and then nonmember would be sound too.

nonmember(_, []).
nonmember(X, [X|_]) :- !,
	fail.
nonmember(X, [_|T]) :-
	nonmember(X, T).