%   File   : MULTIL.PL
%   Author : Lawrence Byrd
%   Updated: 18 May 1983
%   Purpose: Multiple-list routines

%   This module runs compiled.  It needs some things from Util:Applic.Pl
%   The style of programming which would find these routines useful is
%   now frowned upon.  However, you may find their structure instructive.

:- public
	mlmaplist/2,
	mlmaplist/3,
	mlmaplist/4,
	mlmember/2,
	mlselect/3.

:- mode
	mlmaplist(+, +), 
	mlmaplist(+, +, ?),
	mlmaplist(+, +, ?, ?),
	mlmember(?, +),
	mlmember(+, +, ?),
	mlselect(?, +, ?),
	mlselect(+, +, ?, ?),
	ml_putback(+, ?, ?),
	ml_taketop(+, -, -),
	ml_allempty(+).



%   ml_taketop(Lists, Heads, Tails)
%   is true when Lists is a list of non-empty lists, Heads is a list
%   whose elements are the heads of the elements of Lists, and Tails
%   is a list whose elements are the tails of Lists.

ml_taketop([], [], []).
ml_taketop([[Head|Tail]|Lists], [Head|Heads], [Tail|Tails]) :-
	ml_taketop(Lists, Heads, Tails).

%   ml_allempty(Lists)
%   is true when Lists is a list, all of whose elements are nil ([]).
%   It is used to test whether all the lists being mapped over have
%   come to an end at once.  Since ml_taketop will succeed precisely
%   when all the lists have at least one member, we could produce a
%   set of routines that terminate when any list runs out by simply
%   omitting this test.  As it is, the ml* routines demand that all
%   the lists be the same length.

ml_allempty([]).
ml_allempty([[]|Tail]) :-
	ml_allempty(Tail).

%   mlmaplist(Pred, Lists)
%   applies Pred to argument tuples which are successive slices of the Lists.
%   Thus mlmaplist(tidy, [Untidy,Tidied]) would apply tidy([U,T]) to each
%   successive [U,T] pair from Untidy and Tidied.  It isn't tail-recursive,
%   because Pred (and hence apply) may backtrack.

mlmaplist(Pred, Lists) :-
	ml_taketop(Lists, Heads, Tails),
	apply(Pred, [Heads]),
	mlmaplist(Pred, Tails).
mlmaplist(_, Lists) :-
	ml_allempty(Lists).



%   mlmaplist(Pred, Lists, Extra)
%   is like mlmaplist/2, but passes the Extra argument to Pred as well
%   as the slices from the Lists.

mlmaplist(Pred, Lists, Extra) :-
	ml_taketop(Lists, Heads, Tails), !,
	apply(Pred, [Heads, Extra]),
	mlmaplist(Pred, Tails, Extra).
mlmaplist(_, Lists, _) :-
	ml_allempty(Lists).

%   mlmaplist(Pred, Lists, Init, Final)
%   is like mlmaplist/2, but has an extra accumulator feature.  Init is
%   the initial value of the accumulator, and Final is the final result.
%   Pred(Slice, AccIn, AccOut) is called to update the accumulator.

mlmaplist(Pred, Lists, AccOld, AccNew) :-
	ml_taketop(Lists, Heads, Tails),
	!,
	apply(Pred, [Heads, AccOld, AccMid]),
	mlmaplist(Pred, Tails, AccMid, AccNew).
mlmaplist(_, Lists, Accum, Accum) :-
	ml_allempty(Lists).

%   mlmember(Elems, Lists) and mlselect(Elems, Lists, Residues)
%   are the multi-list analogues of member and select.  The definition
%   of mlselect is difficult to blieve; it is almost certainly utterly
%   useless.  But it is retained, as that is how it has always been.
%   Example
%   ml_member([a,d,g], [[a,b,c],[d,e,f],[g,h,i]])
%   is true,
%   ml_member(X, [[a,b,c],[d,e,f],[g,h,i]])
%   instantiates X = [a,d,g]  X = [b,e,h]  X = [c,f,i]

ml_member(Elems, Lists) :-
	ml_taketop(Lists, Heads, Tails), !,
	ml_member(Heads, Tails, Elems).

ml_member(Heads, _, Heads).
ml_member(_, Tails, Elems) :-
	ml_member(Elems, Tails).

ml_select(Elems, Lists, Residues) :-
	ml_taketop(Lists, Heads, Tails),
	!,
	ml_select(Heads, Tails, Elems, Residues).

ml_select(Heads, Tails, Heads, Tails).
ml_select(Heads, Tails, Elems, Residues) :-
	ml_putback(Heads, Rests, Residues), !,
	ml_select(Elems, Tails, Rests).

%   ml_putback(+Heads, ?Tails, ?Lists)
%   is true when ml_taketop(Lists, Heads, Tails) is true, but is
%   rearranged for efficiency with different calling pattern.  It
%   only exists for the benefit of ml_select, and as the bug in the
%   latter went unnnoticed for 3 years, I) don't suppose it matters
%   much.

ml_putback([], [], []).
ml_putback([Head|Heads], [Tail|Tails], [[Head|Tail]|Lists]) :-
	ml_putback(Heads, Tails, Lists).




%   ml_putback(+Heads, ?Tails, ?Lists)
%   is true when ml_taketop(Lists, Heads, Tails) is true, but is
%   rearranged for efficiency with different calling pattern.  It
%   only exists for the benefit of mlselect, and as the bug in the
%   latter went unnnoticed for 3 years, I) don't suppose it matters
%   much.

ml_putback([], [], []).
ml_putback([Head|Heads], [Tail|Tails], [[Head|Tail]|Lists]) :-
	ml_putback(Heads, Tails, Lists).