<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
% Predicate for findall difference list implementation
% Martti Meri, 9.11.2005

% see Sterling and Shapiro, Chapter 16 p. 304.

% A usefull remark by Richard A. O'Keefe :
% http://gollem.science.uva.nl/SWI-Prolog/mailinglist/archive/old/0924.html
% goes as follows:
/*
To start with, there is no such animal as a difference list.
There isn't a special kind of list called a difference list.
What we _do_ have is a special kind of difference called a 
list difference, that is, L1 \ L2 where L1 and L2 are both
lists and L2 is a tail of L1.

More precisely,

    L1, L2 are the components of a list difference
    if and only if they are (or will be) lists and
    there is (or will be) a list L3 such that
    append(L3, L2, L1).  In this case, L3 is the
    difference of the lists L1 and L2.
*/

:-op(954,xfy,\).  % use \ to mark list difference

% see help(style_check) for setting style_check(+dollar) to
% avoid encircling $instance and $mark in hyphens below.

% predicate for findall difference list implementation

find_all_dl(X,Goal,_)  :-
        asserta('$instance'('$mark')),
        Goal,
        asserta('$instance'(X)),
        print_instances,
        fail.                            
find_all_dl(X,_,Xs\Ys)  :-
        retract('$instance'(X)),        
        reap(X,Xs\Ys),
        !.

% So, a mark is asserted and then the Goal predicate repetitively
% succeeds each time followed by assertion of the solution to the data
% base.  The strings '$instance' and '$mark' are quiter arbitrary and 
% could be replaced by almost anything.  What the authors try to
% indicate here is that these are something which have internal system 
% predicate use and should be named so that they
% don't (easily) collide with the definitions users (prolog programmers) are 
% likely to put in use.
% The second version of the find_all_dl generates a second phase 
% in the operations of the program, each success of the predicate 
% handles one asserted instance in the data base.


reap(X,Xs\Ys) :-
        print_instances,
        X \= '$mark',
        retract('$instance'(X1)), !,
        reap(X1,Xs\[X|Ys]),
        write([diff_list_head,Xs]),nl,
        write([diff_list_tail,[X| Ys]]),nl,nl.
reap('$mark',Xs\Xs) :-
        print_instances,
        write([diff_list_head_at_mark,Xs]),nl,
        write([diff_list_tail_at_mark,Xs]),nl.


% In the first version of the reap the recursive call puts X in the
% beginning of the tail of the difference list.  When mark is met
% the head and tail are unified.  
% Xs/Xs generates an empty list at the end of the search.  The list elements 
% are pushed to the latter part of the A \ B structure.  And this B has a 
% variable at the end.  So the Xs/Xs causes unification and The last
% Ys is left unbound so a variable to indicate some unbound B part of
% the list difference structure. 


% some arbitrary domain model

tie(helsinki,salo).
tie(salo,turku).
tie(turku,forssa).
tie(helsinki,hameenlinna).
tie(hameenlinna,tampere).
tie(tampere,forssa).

% use standard findall to gather all asserted '$instance' predicates
print_instance :-
        findall(X,call('$instance'(X)),Xs),
        write(Xs),nl,
        fail.
                  
print_instances :-
        \+print_instance,
        nl.


% Example runs:
% Compare what the difference list and the conventional versions do.

% Finding all places where a road (tie) goes to (too roads go to forssa)

/*

?- find_all_dl(X,tie(_,X),Xs).
[salo, $mark]
 
[turku, salo, $mark]
 
[forssa, turku, salo, $mark]
 
[hameenlinna, forssa, turku, salo, $mark]
 
[tampere, hameenlinna, forssa, turku, salo, $mark]
 
[forssa, tampere, hameenlinna, forssa, turku, salo, $mark]
 
[tampere, hameenlinna, forssa, turku, salo, $mark]
 
[hameenlinna, forssa, turku, salo, $mark]
 
[forssa, turku, salo, $mark]
 
[turku, salo, $mark]
 
[salo, $mark]
 
[$mark]
 
[]
 
[]
 
[diff_list_head_at_mark, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail_at_mark, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_head, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
 
[diff_list_head, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail, [turku, forssa, hameenlinna, tampere, forssa|_G263]]
 
[diff_list_head, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail, [forssa, hameenlinna, tampere, forssa|_G263]]
 
[diff_list_head, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail, [hameenlinna, tampere, forssa|_G263]]
 
[diff_list_head, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail, [tampere, forssa|_G263]]
 
[diff_list_head, [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]]
[diff_list_tail, [forssa|_G263]]
 
 
X = forssa
Xs = [salo, turku, forssa, hameenlinna, tampere, forssa|_G263]\_G263 ;
 
No
?-
*/

% A more pathological example, but like for the standard findall the
% difference list version returns empty list. 

% find_all_dl(X,(\+tie(X,Y),\+tie(Y,X)),Xs).
% findall(X,(\+tie(X,Y),\+tie(Y,X)),Xs).

/*

?- find_all_dl(X,(\+tie(X,Y),\+tie(Y,X)),Xs).
[]
 
[]
 
[diff_list_head_at_mark, _G294]
[diff_list_tail_at_mark, _G294]
 
X = '$mark'
Y = _G184
Xs = _G294\_G294 ;
 
No
?-
?- findall(X,(\+tie(X,Y),\+tie(Y,X)),Xs).
 
X = _G183
Y = _G184
Xs = [] ;
 
No

*/

% more complex example predicates would require implementing the set
% operations for delete lists.  Neither the Sterling &amp; Shapiro nor 
% SWI-Prolog manuals do a very good job in explaining the local and
% hidden predicates and the use of $ in or outside of hyphens.  An
% example where namings collide because of visibility and the phenomenon
% concerning the things that happen if you omit $mark would be wellcomed.
%
</pre></body></html>