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.137Eventually 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-19T11:10:51):2 upvotes 2 0 downvotes
Picture of user LogicalCaptain.

This predicate does not backtrack (which is why it exists).

Use this predicate instead of member/2 if you know you need it (to wring efficiency out of a program) and you know enough about Elem and List to be sure this predicate is appropriate.

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

Bag = [one].

but:

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

Bag = [one, two, three].

In fact, memberchk/2 may well be implemented as

memberchk(Elem, List) :- once(member(Elem, List)).

and maybe it's clearer to actually write once(member(Elem, List)) in your code.

Watch out for unexpected failure (from the paper Indexing dif/2)

?- X=2, memberchk(X, [1,2]), X=2
X=2.    % expected solution

?-      memberchk(X, [1,2]), X=2.
false.  % unexpected failure

?-      member(X, [1,2]), X=2.
X = 2.

Going one further: considering unbound variables as list elements

This may not be the appropriate place for this note but what if you want to consider unbound variables as elements to be manipulated, not placeholders to be instantiated?

For example:

Is foo a member of [1,2,X,Y] according to member/2?

There are two solutions (which partially overlap for X=Y=foo):

?- member(foo,[1,2,X,Y]).
X = foo ;
Y = foo.

Is foo a member of [1,2,X,Y] according to memberchk/2? There is one answer:

?- memberchk(foo,[1,2,X,Y]).
X = foo.

But what if you do not want to unify and consider variables as "objects" to be worked on (in fact, your are reasoning about the "list program object" itself, not what it stands for):

?- in_prefix(foo,[1,2,X,Y]).
false.

?- in_prefix(Y,[1,2,X]).
false.

?- in_prefix(Y,[1,2,Y]).
true.

?- Y=4,in_prefix(Y,[1,2,Y]).
Y = 4.

It can be done: