Did you know ... | Search Documentation: |

Predicate subtract/3 |

- Documentation
- Reference manual
- The SWI-Prolog library
- library(lists): List Manipulation
- member/2
- append/3
- append/2
- prefix/2
- select/3
- selectchk/3
- select/4
- selectchk/4
- nextto/3
- delete/3
- nth0/3
- nth1/3
- nth0/4
- nth1/4
- last/2
- proper_length/2
- same_length/2
- reverse/2
- permutation/2
- flatten/2
- clumped/2
- max_member/2
- min_member/2
- max_member/3
- min_member/3
- sum_list/2
- max_list/2
- min_list/2
- numlist/3
- is_set/1
- list_to_set/2
- intersection/3
- union/3
- subset/2
- subtract/3

- library(lists): List Manipulation

- The SWI-Prolog library
- Packages

- Reference manual

`|`

`|`

*`|`

`|`

.
A
- See also
- ord_subtract/3.

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*.

?- 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].

?- 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

Tags: