ok@quintus.UUCP (Richard A. O'Keefe) (04/15/88)
Just recently I came across yet another version of findall and I thought
I'd share it with you. I've changed the names around a bit to disguise
the original, but I haven't changed the way it works.
:- dynamic
stack_of_difference_lists/2.
findall(Term, Goal, _) :-
asserta(stack_of_difference_lists(Tail,Tail)),
call(Goal),
add_solution(Term),
fail.
findall(_, _, List) :-
stack_of_difference_lists(List, []),
retract(stack_of_difference_lists(_,_)),
!.
add_solution(Term) :-
stack_of_difference_lists(List, [Term|Tail]),
retract(stack_of_difference_lists(_,_)),
asserta(stack_of_difference_lists(List,Tail)),
!.
Do I need to point out the bug? One symptom is that the query
| ?- findall(X-Y, (
member(X, [[1],[2,3]]),
findall(L, member(L, X), [Y])
), Z).
should return the solution Z = [[1]-1], but instead it yields the
wrong answer Z = [[1]-1,[2,3]- ([1]-1)].
Mind you, it was clever of the author to use a difference list representation
in the data base, it must reduce the quadratic cost of this code by several
percent. The Clocksin & Mellish method, with a separate assertion for each
solution found, is of course linear, not quadratic. Delicious.
You'll recall that I call the way findall/3 or whatever is coded "the
Touchstone" to indicate that it is useful as a way of testing whether
you've got gold or pyrites. Did it prove reliable as an indicator of
the quality of the rest of the code? Too right!