Findall/3 Without Copying?

Appeared in Volume 9/1, February 1996

Keywords: findall.

etg10@cl.cam.ac.uk
Edmund Grimley-Evans
23rd November 1995

I have a neat, lucid and elegant way of doing something with findall/3, but unfortunately it's hopelessly inefficient because of the way findall/3 copies its solutions. Or worse still it's unusable because I have to preserve the identity of variables.

A very simple example of the problem is:

tail(A,A).
tail([_|A],B) :- tail(A,B).

tails(X,Y) :- findall(A,tail(X,A),Y).

What I really want is:

tails1(List,[List|Rest]) :- 
    tails2(List,Rest).

tails2([],[]).
tails2([_|Rest],[Rest|More]) :-
    tails2(Rest,More).

Is there any general way of getting all solutions without copying all of the structures? I can see that a non-copying findall/3 would not be well-defined, but is there some other systematic approach that I could adopt in this sort of situation?

pereira@research.att.com
Fernando Pereira
23rd November 1995

findall/3 is an "or" iterator, while what you want is an "and" iterator, in the style of the fold family of higher-order functions in functional programming. Assume for the moment that your Prolog has a built-in "higher-order" call (this can be provided or simulated in various ways, cf. the discussions on call/N in comp.lang.prolog some time ago). Assume we have the library predicate:

map(_Pred, [], Result, Result).
map(Pred, [Elem|Rest], Result, Result0) :-
    Pred([Elem|Rest], Result1, Result),
    map(Pred, Rest, Result1, Result0).

Then define:

tails(List, Tails) :- 
    map(tail, List, Tails, []).

tail([_|Tail], Tails, [Tail|Tails]).

Many variants of this are possible.