• Places
    • Home
    • Graphs
    • Prefixes
  • Admin
    • Users
    • Settings
    • Plugins
    • Statistics
  • CPACK
    • Home
    • List packs
    • Submit pack
  • Repository
    • Load local file
    • Load from HTTP
    • Load from library
    • Remove triples
    • Clear repository
  • Query
    • YASGUI SPARQL Editor
    • Simple Form
    • SWISH Prolog shell
  • Help
    • Documentation
    • Tutorial
    • Roadmap
    • HTTP Services
  • Login

A The SWI-Prolog library
AllApplicationManualNameSummaryHelp

  • Documentation
    • Reference manual
      • The SWI-Prolog library
        • library(aggregate): Aggregation operators on backtrackable predicates
        • library(ansi_term): Print decorated text to ANSI consoles
        • library(apply): Apply predicates on a list
        • library(assoc): Association lists
        • library(broadcast): Broadcast and receive event notifications
        • library(charsio): I/O on Lists of Character Codes
        • library(check): Consistency checking
        • library(clpb): CLP(B): Constraint Logic Programming over Boolean Variables
        • library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains
        • library(clpqr): Constraint Logic Programming over Rationals and Reals
        • library(csv): Process CSV (Comma-Separated Values) data
        • library(dcg/basics): Various general DCG utilities
        • library(dcg/high_order): High order grammar operations
        • library(debug): Print debug messages and test assertions
        • library(dicts): Dict utilities
        • library(error): Error generating support
        • library(fastrw): Fast reading and writing of terms
        • library(gensym): Generate unique symbols
        • library(heaps): heaps/priority queues
        • library(increval): Incremental dynamic predicate modification
        • library(intercept): Intercept and signal interface
        • library(iostream): Utilities to deal with streams
        • library(listing): List programs and pretty print clauses
        • library(lists): List Manipulation
        • library(main): Provide entry point for scripts
        • library(nb_set): Non-backtrackable set
        • library(www_browser): Open a URL in the users browser
        • library(occurs): Finding and counting sub-terms
        • library(option): Option list processing
        • library(optparse): command line parsing
        • library(ordsets): Ordered set manipulation
          • is_ordset/1
          • ord_empty/1
          • ord_seteq/2
          • list_to_ord_set/2
          • ord_intersect/2
          • ord_disjoint/2
          • ord_intersect/3
          • ord_intersection/2
          • ord_intersection/3
          • ord_intersection/4
          • ord_add_element/3
          • ord_del_element/3
          • ord_selectchk/3
          • ord_memberchk/2
          • ord_subset/2
          • ord_subtract/3
          • ord_union/2
          • ord_union/3
          • ord_union/4
          • ord_symdiff/3
        • library(pairs): Operations on key-value lists
        • library(persistency): Provide persistent dynamic predicates
        • library(pio): Pure I/O
        • library(portray_text): Portray text
        • library(predicate_options): Declare option-processing of predicates
        • library(prolog_debug): User level debugging tools
        • library(prolog_jiti): Just In Time Indexing (JITI) utilities
        • library(prolog_pack): A package manager for Prolog
        • library(prolog_xref): Prolog cross-referencer data collection
        • library(quasi_quotations): Define Quasi Quotation syntax
        • library(random): Random numbers
        • library(rbtrees): Red black trees
        • library(readutil): Read utilities
        • library(record): Access named fields in a term
        • library(registry): Manipulating the Windows registry
        • library(settings): Setting management
        • library(statistics): Get information about resource usage
        • library(strings): String utilities
        • library(simplex): Solve linear programming problems
        • library(solution_sequences): Modify solution sequences
        • library(tables): XSB interface to tables
        • library(terms): Term manipulation
        • library(thread): High level thread primitives
        • library(thread_pool): Resource bounded thread management
        • library(ugraphs): Graph manipulation library
        • library(url): Analysing and constructing URL
        • library(varnumbers): Utilities for numbered terms
        • library(yall): Lambda expressions
    • Packages

A.31 library(ordsets): Ordered set manipulation

Ordered sets are lists with unique elements sorted to the standard order of terms (see sort/2). Exploiting ordering, many of the set operations can be expressed in order N rather than N^2 when dealing with unordered sets that may contain duplicates. The library(ordsets) is available in a number of Prolog implementations. Our predicates are designed to be compatible with common practice in the Prolog community. The implementation is incomplete and relies partly on library(oset), an older ordered set library distributed with SWI-Prolog. New applications are advised to use library(ordsets).

Some of these predicates match directly to corresponding list operations. It is advised to use the versions from this library to make clear you are operating on ordered sets. An exception is member/2. See ord_memberchk/2.

The ordsets library is based on the standard order of terms. This implies it can handle all Prolog terms, including variables. Note however, that the ordering is not stable if a term inside the set is further instantiated. Also note that variable ordering changes if variables in the set are unified with each other or a variable in the set is unified with a variable that isā€˜older' than the newest variable in the set. In practice, this implies that it is allowed to use member(X, OrdSet) on an ordered set that holds variables only if X is a fresh variable. In other cases one should cease using it as an ordset because the order it relies on may have been changed.

[semidet]is_ordset(@Term)
True if Term is an ordered set. All predicates in this library expect ordered sets as input arguments. Failing to fullfil this assumption results in undefined behaviour. Typically, ordered sets are created by predicates from this library, sort/2 or setof/3.
[semidet]ord_empty(?List)
True when List is the empty ordered set. Simply unifies list with the empty list. Not part of Quintus.
[semidet]ord_seteq(+Set1, +Set2)
True if Set1 and Set2 have the same elements. As both are canonical sorted lists, this is the same as ==/2.
Compatibility
sicstus
[det]list_to_ord_set(+List, -OrdSet)
Transform a list into an ordered set. This is the same as sorting the list.
[semidet]ord_intersect(+Set1, +Set2)
True if both ordered sets have a non-empty intersection.
[semidet]ord_disjoint(+Set1, +Set2)
True if Set1 and Set2 have no common elements. This is the negation of ord_intersect/2.
ord_intersect(+Set1, +Set2, -Intersection)
Intersection holds the common elements of Set1 and Set2.
deprecated
Use ord_intersection/3
[semidet]ord_intersection(+PowerSet, -Intersection)
Intersection of a powerset. True when Intersection is an ordered set holding all elements common to all sets in PowerSet. Fails if PowerSet is an empty list.
Compatibility
sicstus
[det]ord_intersection(+Set1, +Set2, -Intersection)
Intersection holds the common elements of Set1 and Set2. Uses ord_disjoint/2 if Intersection is bound to [] on entry.
[det]ord_intersection(+Set1, +Set2, ?Intersection, ?Difference)
Intersection and difference between two ordered sets. Intersection is the intersection between Set1 and Set2, while Difference is defined by ord_subtract(Set2, Set1, Difference).
See also
ord_intersection/3 and ord_subtract/3.
[det]ord_add_element(+Set1, +Element, ?Set2)
Insert an element into the set. This is the same as ord_union(Set1, [Element], Set2).
[det]ord_del_element(+Set, +Element, -NewSet)
Delete an element from an ordered set. This is the same as ord_subtract(Set, [Element], NewSet).
[semidet]ord_selectchk(+Item, ?Set1, ?Set2)
Selectchk/3, specialised for ordered sets. Is true when select(Item, Set1, Set2) and Set1, Set2 are both sorted lists without duplicates. This implementation is only expected to work for Item ground and either Set1 or Set2 ground. The "chk" suffix is meant to remind you of memberchk/2, which also expects its first argument to be ground. ord_selectchk(X, S, T) => ord_memberchk(X, S) & \+ ord_memberchk(X, T).
author
Richard O'Keefe
[semidet]ord_memberchk(+Element, +OrdSet)
True if Element is a member of OrdSet, compared using ==. Note that enumerating elements of an ordered set can be done using member/2.

Some Prolog implementations also provide ord_member/2, with the same semantics as ord_memberchk/2. We believe that having a semidet ord_member/2 is unacceptably inconsistent with the *_chk convention. Portable code should use ord_memberchk/2 or member/2.

author
Richard O'Keefe
[semidet]ord_subset(+Sub, +Super)
Is true if all elements of Sub are in Super
[det]ord_subtract(+InOSet, +NotInOSet, -Diff)
Diff is the set holding all elements of InOSet that are not in NotInOSet.
[det]ord_union(+SetOfSets, -Union)
True if Union is the union of all elements in the superset SetOfSets. Each member of SetOfSets must be an ordered set, the sets need not be ordered in any way.
author
Copied from YAP, probably originally by Richard O'Keefe.
[det]ord_union(+Set1, +Set2, -Union)
Union is the union of Set1 and Set2
[det]ord_union(+Set1, +Set2, -Union, -New)
True iff ord_union(Set1, Set2, Union) and ord_subtract(Set2, Set1, New).
[det]ord_symdiff(+Set1, +Set2, ?Difference)
Is true when Difference is the symmetric difference of Set1 and Set2. I.e., Difference contains all elements that are not in the intersection of Set1 and Set2. The semantics is the same as the sequence below (but the actual implementation requires only a single scan).
      ord_union(Set1, Set2, Union),
      ord_intersection(Set1, Set2, Intersection),
      ord_subtract(Union, Intersection, Difference).

For example:

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

ClioPatria (version V3.1.1-42-gd6a756b-DIRTY)