Subject: Re: Re[1]: subtract/3

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 12 Jun 2000 10:39:52 +1200 (NZST)

Lionel wrote:
	Yes, but writing that this predicate handles sets doesn't 
	mean that it also handles lists.
	If I'm not wrong, "sets" are a subset of "lists".
	I wanted to be sure that I could safely use lists with this 
	predicate.
	
"Safely" in the sense that it won't crash the machine, yes.
"Safely" in the sense that it will give the result you expect:
 but what result *do* you expect?  That's the question.
There are dozens of ways to write set difference in Prolog, and
they don't all do the same thing with lists that are not sets.

Here is the version of sets:subtract/3 from the Quintus Prolog library:

%   subtract(+Set1, +Set2, ?Difference)
%   is like intersect, but this time it is the elements of Set1 which
%   *are* in Set2 that are deleted.  Note that duplicated Elements of
%   Set1 which are not in Set2 are retained in Difference.

subtract([], _, []).
subtract([Element|Elements], Set, Difference) :-
    memberchk(Element, Set),
    !,
    subtract(Elements, Set, Difference).
subtract([Element|Elements], Set, [Element|Difference]) :-
    subtract(Elements, Set, Difference).

But here is another one, which returns exactly the same result when
Set1 is a set (has no duplicates), but always returns a set.

subtract([], _, []).
subtract([Element|Elements], Set, Difference) :-
    memberchk(Element, Set),
    !,
    subtract(Elements, Set, Difference).
subtract([Element|Elements], Set, [Element|Difference]) :-
    subtract(Elements, [Element|Set], Difference).

And here's another one, which returns the same _set_ as the second,
but usually in a different order:

subtract(Set1, Set2, Difference) :-
    sort(Set1, OrdSet1),
    sort(Set2, OrdSet2),
    ordsets:subtract(OrdSet1, OrdSet2, Difference).

Really, the predicate is so short that if you depend on some specific
behaviour for lists with duplicates, it's less effort to write exactly
what you want (and document the behaviour that matters) than to poke
around and find what some existing thing does outside its domain of
definition.