Did you know ... Search Documentation:
Predicate memberchk/2
Availability:built-in
Source[semidet]memberchk(?Elem, +List)
True when Elem is an element of List. This‘chk' variant of member/2 is semi deterministic and typically used to test membership of a list. Raises a type error if scanning List encounters a non-list. Note that memberchk/2 does not perform a full list typecheck. For example, memberchk(a, [a|b]) succeeds without error. If List is cyclic and Elem is not a member of List, memberchk/2 eventually raises a type error.136Eventually here means it will scan as many elements as the longest list that may exist given the current stack usage before raising the exception.

Examples

What is wrong with intersection/3 and friends?

What is wrong with intersection/3 and friends?

The library(lists) contains a number of old predicates for manipulating sets represented as unordered lists, notably intersection/3, union/3, subset/2 and subtract/3. These predicates all use memberchk/2 to find equivalent elements. As a result these are not logical while unification can easily lead to dubious results. Operating on unordered sets these predicates typically have complexity |Set1|*|Set2|.

When using these predicates

  • Make sure to respect the mode, i.e., make sure the input lists are proper lists. See is_list/1.
  • Make sure elements are sufficiently instantiated such that their equality can safely be checked using unification. See ?=/2.
  • Make sure the inputs are indeed sets, i.e., the lists contain no duplicates. In this case, a list is considered to have a duplicate if two members of the list can unify.

Intended behavior

?- intersection([a,b,c], [b,e], X).
X = [b].
?- union([a,b,c], [b,e], X).
X = [a, c, b, e].
?- subset([a,b,c], [b,e]).
false.
?- subset([b], [b,e]).
true.
?- subtract([a,b,c], [b,e], X).
X = [a, c].

Dubious behavior

?- intersection([a,b,c], [b,E], X).
E = a,
X = [a, b].
?- subtract([a,b,c], [b,E], X).
E = a,
X = [c].

Insufficient instantiation also leads to problems

?- subtract([a,b,c], X, [c]).
false.

Note that duplicates in the input may result in duplicates in the output (example by Boris).

?- intersection([a,b,a], [b,a,b], I).
I = [a, b, a].
deprecated
- New code should use library(ordsets) instead.
Tags are associated to your profile if you are logged in|Report abuse
Tags:
  • doc-needs-help
LogicalCaptain said (2016-12-19T03:10:51):0 upvotes 0 0 downvotes
Picture of user LogicalCaptain.

This predicate does not backtrack:

?- findall(X, memberchk(X, [one,two,three]), Bag).

Bag = [one].

but:

?- findall(X, member(X, [one,two,three]), Bag).

Bag = [one, two, three].