library(nb_set) defines non-backtrackable
sets, implemented as binary trees. The sets are represented as
compound terms and manipulated using nb_setarg/3.
Non-backtrackable manipulation of data structures is not supported by a
large number of Prolog implementations, but it has several advantages
over using the database. It produces less garbage, is thread-safe,
reentrant and deals with exceptions without leaking data.
Similar to the
library(assoc) library, keys can be any
Prolog term, but it is not allowed to instantiate or modify a term.
One of the ways to use this library is to generate unique values on
backtracking without generating all solutions first,
for example to act as a filter between a generator producing many
duplicates and an expensive test routine, as outlined below:
add_nb_set(Solution, Set, true),
- True if Set is a non-backtrackable empty set.
- Add Key to Set. If Key is already a
succeeds without modifying Set.
- If Key is not in Set and New is unified
true, Key is added to Set. If Key
is in Set, New is unified to
It can be used for many purposes:
add_nb_set(+, +, false)
|Test membership |
add_nb_set(+, +, true)
|Succeed only if new
add_nb_set(+, +, Var)
|Succeed, binding Var |
- Generate all members of Set on backtracking in the standard
order of terms. To test membership, use add_nb_set/3.
- Unify Size with the number of elements in Set.
- Unify List with a list of all elements in Set in
the standard order of terms (i.e., an ordered list).