1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
\libdoc{nb_set}{Non-backtrackable set}
The library \pllib{nb_set} defines \jargon{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 \pllib{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 \emph{without} generating \emph{all} solutions first,
for example to act as a filter between a generator producing many
duplicates and an expensive test routine, as outlined below:
\begin{code}
generate_and_test(Solution) :-
empty_nb_set(Set),
generate(Solution),
add_nb_set(Solution, Set, true),
test(Solution).
\end{code}
\begin{description}
\predicate{empty_nb_set}{1}{?Set}
True if \arg{Set} is a non-backtrackable empty set.
\predicate{add_nb_set}{2}{+Key, !Set}
Add \arg{Key} to \arg{Set}. If \arg{Key} is already a member of
\arg{Set}, add_nb_set/3 succeeds without modifying \arg{Set}.
\predicate{add_nb_set}{3}{+Key, !Set, ?New}
If \arg{Key} is not in \arg{Set} and \arg{New} is unified to
\const{true}, \arg{Key} is added to \arg{Set}. If \arg{Key}
is in \arg{Set}, \arg{New} is unified to \const{false}. It can
be used for many purposes:
\begin{center}
\begin{tabular}{ll}
\tt add_nb_set(+, +, false) & Test membership \\
\tt add_nb_set(+, +, true) & Succeed only if new member \\
\tt add_nb_set(+, +, Var) & Succeed, binding \arg{Var} \\
\end{tabular}
\end{center}
\predicate{gen_nb_set}{2}{+Set, -Key}
Generate all members of \arg{Set} on backtracking in the standard order
of terms. To test membership, use add_nb_set/3.
\predicate{size_nb_set}{2}{+Set, -Size}
Unify \arg{Size} with the number of elements in \arg{Set}.
\predicate{nb_set_to_list}{2}{+Set, -List}
Unify \arg{List} with a list of all elements in \arg{Set} in the standard
order of terms (i.e., an \jargon{ordered list}).
\end{description}
|
