Ordered Sets¶
The following ordered set manipulation routines are available once included with the use_module(library(ordsets)) command.
An ordered set is represented by a list having unique and ordered elements. Output arguments are guaranteed to be ordered sets, if the relevant inputs are. This is a slightly patched version of Richard O'Keefe's original library.
In this module, sets are represented by ordered lists with no duplicates. Thus {c,r,a,f,t} would be [a,c,f,r,t]. The ordering is defined by the < family of term comparison predicates, which is the ordering used by sort//22 and setof//33.
The benefit of the ordered representation is that the elementary set operations can be done in time proportional to the Sum of the argument sizes rather than their Product. Some of the unordered set routines, such as member//22, length//22, select//33 can be used unchanged. The main difficulty with the ordered representation is remembering to use it!
- ord_setproduct/4
- ord_union/6
- ord_symdiff/3
- ord_intersection/7
- list_to_ord_set/2
- ord_union/5
- ord_union/4
- ord_symdiff/4
- ord_subtract/4
- ord_subset/3
- ord_seteq/3
- ord_intersection/5
- ord_insert/4
- ord_disjoint/3
- ord_del_element/4
- ord_add_element/4
- prolog::ord_memberchk/2
- prolog::ord_empty/1
- prolog::ord_union/2
- prolog::ord_member/2
- prolog::ord_setproduct/3
- prolog::ord_union/3
- prolog::ord_del_element/3
- prolog::ord_subtract/3
- prolog::ord_subset/2
- prolog::ord_seteq/2
- prolog::ord_intersection/4
- prolog::ord_intersection/3
- prolog::ord_intersect/3
- prolog::ord_insert/3
- prolog::ord_add_element/3
- prolog::ord_disjoint/2
- prolog::merge/3
Functions:¶
1. *** prolog::list_to_ord_set(+List, ?Set) % is true when Set is the ordered representation of the set represented% by the unordered representation List. The only reason for giving it% a name at all is that you may not have realised that @ref sortU2fU_2 "sort class list_to_ord_set_2 *:
1. *** prolog::ord_intersect(+Set1,+Set2) % is true when the two ordered sets have at least one element in common.% Note that the test is `*:
1. *** prolog::ord_intersection(+Set1,+Set2, ?Intersection) % is true when Intersection is the ordered representation of Set1% and Set2*:
1. *** prolog::ord_intersection(+Set1,+Set2, ?Intersection, ?Difference) % is true when Intersection is the ordered representation of Set1% and Set2*:
1. *** prolog::ord_union(+Set1,+Set2, ?Union, ?Difference) % is true when Union is the union of Set1 and Set2 and Difference is the% difference between Set2 and Set1. class ord_union_4*:
1. *** prolog::ord_setproduct(+Set1,+Set2, ?Product) % is in fact identical to setproduct(Set1*:
Var:¶
1. Product If Set1 and Set2 are ordered Product will be an ordered set of x1 x2 pairs Note that we cannot solve for Set1 and prolog::Se/2: