153: Ordered sets

by John Cowan

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-153@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

Osets are immutable collections that can contain any Scheme objects as long as a total order exists among the objects. Osets enforce the constraint that no two elements can be the same in the sense of the oset's associated equality predicate. The elements in an oset appear in a fixed order determined by the comparator used to create it.

Rationale

The names in this SRFI are harmonized with the names used in SRFI 113 and SRFI 146.

It's possible to use the general osets of this SRFI to contain characters, but the use of SRFI 14 is recommended instead.

Osets do not have a lexical syntax representation. It's possible to use SRFI 108 quasi-literal constructors to create them in code, but this SRFI does not standardize how that is done.

The interface to general osets depends on SRFI 128 comparators. Comparators conveniently package the equality predicate of the oset with the ordering predicate needed to implement the oset efficiently.

In Java and Smalltalk terminology, the sets of this SRFI are sorted (in the sense of the comparator) rather than ordered (by insertion).

Rationale for oset-accumulate

As well as sometimes leading to more compact expressions than the traditional three-procedure unfold, oset-accumulate may be more efficient when the programmer wants the value of each new seed to depend on the computed key and value. For example, assume that we apply some procedure f to a seed s to get a element e, and that we also want to compute a new seed from e. Using oset-unfold, we'd have no choice other than to compute e twice:


    (oset-unfold stop?
                 f
                 (lambda (s)
                   (let* ((e (f s))
                          ((s* …)))
                       s*)))
                 seed)

Using oset-accumulate, however, it's easy to write an equivalent unfold which computes e only once for each step:


    (oset-accumulate (lambda (terminate s)
                        (if (stop? s)
                            (terminate)
                            (let* ((e (f s))
                                   ((s* …)))
                                (values e s*)))))
                        seed)

This may be preferable when f is expensive to apply or entails side effects.

Per contra, calling terminate entails abandoning the current continuation, which may be more expensive than simply invoking stop.

Specification

Osets are disjoint from other types of Scheme objects.

It is an error for any procedure defined in this SRFI to be invoked on osets with distinct comparators (in the sense of eq?).

It is an error to mutate any object while it is contained in an oset in such a way as to make it no longer the same (in the sense of the comparator) as its previous state.

It is an error to add an object to an oset which does not satisfy the type test predicate of the comparator.

It is an error to add or remove an object for an oset or while iterating over it.

It is an error if comparators used with the procedures of this SRFI do not provide an ordering predicate. It is not necessary for them to provide a hash function.

The procedures of this SRFI are "pure functional" — they do not alter their parameters.

Procedure index

Oset procedures

Constructors

(oset comparator element ... )

Returns an oset containing elements. The comparator argument is a SRFI 128 comparator, which is used to control and distinguish the elements of the oset.

(oset/ordered comparator element ... )

The same as oset, except that it is an error if the elements are not in order (in the sense of the comparator). May be implemented more efficiently than oset.

(oset-unfold stop? mapper successor seed comparator)

Create an oset as if by oset using comparator. If the result of applying the predicate stop? to seed is true, return the oset. Otherwise, apply the procedure mapper to seed. The value that mapper returns is added to the oset. Then get a new seed by applying the procedure successor to seed, and repeat this algorithm.

(oset-unfold/ordered stop? mapper successor seed comparator)

The same as oset-unfold, except that it is an error if the elements are not generated in order (in the sense of the comparator). May be implemented more efficiently than oset.

(oset-accumulate proc comparator seed₁ seed₂ …) → oset

Similar to oset-unfold, except that a single procedure controls the unfolding of a new oset. Let n be the number of seeds. The procedure proc is applied to a procedure terminate and the seeds, in that order, and is expected to return n + 1 values: a new element and n new seed values. The element is added to the new oset, and unfolding continues with the new seeds. If, instead, terminate is invoked on any number of arbitrary values, then the new oset along with the arguments passed to terminate are returned from oset-accumulate.

It is an error for the number of seeds to vary between steps of the unfolding process. If different steps of this process produce equal elements (in the sense of the comparator), then the first such element prevails.

Example:


    (let-values (((oset s)
                  (oset-accumulate
                   (lambda (terminate i)
                     (if (< i -3)
                         (terminate 'finished)
                         (values i (- i 1))))
                   -1)))
      (values oset->list oset) s))
     ⇒ (-3 -2 -1)
       finished

Predicates

(oset? obj)

Returns #t if obj is an oset, and #f otherwise.

(oset-contains? oset element)

Returns #t if element is a member of oset, and #f otherwise.

(oset-empty? oset)

Returns #t if oset has no elements, and #f otherwise.

(oset-disjoint? oset1 oset2)

Returns #t if oset1 and oset2 have no elements in common, and #f otherwise.

Accessors

(oset-member oset element default)

Returns the element of oset that is equal, in the sense of oset's equality predicate, to element. If element is not a member of oset, default is returned.

(oset-element-comparator oset)

Returns the comparator used to compare the elements of oset.

Updaters

(oset-adjoin oset element ...)

The oset-adjoin procedure returns an oset that uses the same comparator as oset and contains all its elements plus the elements. If some element is the same as some element of oset (in the sense of oset's comparator), the existing element prevails.

(oset-adjoin/replace oset element ...)

The oset-adjoin procedure returns an oset that uses the same comparator as oset and contains all its elements plus the elements. If some element is the same as some element of oset (in the sense of oset's comparator), the new element prevails.

(oset-delete oset element ...)

The oset-delete procedure returns an oset containing all the values of oset except for any that are equal (in the sense of oset's comparator) to one or more of the elements. Any element that is not equal to some member of the oset is ignored.

(oset-delete-all oset element-list)

The oset-delete-all procedure is the same as oset-delete, except that it accepts a single argument, which is a list of elements to be deleted.

(oset-pop oset [ failure ])
(oset-pop/reverse oset [ failure ])

The oset-pop procedure chooses the smallest/largest element (in the sense of the comparator of oset) from oset and returns two values, a newly allocated oset that uses the same comparator as oset and contains all associations of oset except the chosen one, and the chosen element itself. If oset contains no such element and failure is supplied, then failure is invoked in tail context on no arguments and its values returned. Otherwise, it is an error.

The whole oset

(oset-size oset)

Returns the number of elements in oset as an exact integer.

(oset-find predicate oset failure)

Returns the first element of oset that satisfies predicate, or the result of invoking the single-valued thunk failure if there is none.

(oset-count predicate oset)

Returns the number of elements of oset that satisfy predicate as an exact integer.

(oset-any? predicate oset)

Returns #t if any element of oset satisfies predicate, or #f otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the oset.

(oset-every? predicate oset)

Returns #t if every element of oset satisfies predicate, or #f otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the oset.

Mapping and folding

(oset-map proc comparator oset)

Applies proc to each element of oset in order and returns an oset, created as if by (oset comparator), which contains the results of the applications. For example:

        (oset-map string-ci-comparator
                  symbol->string
                  (oset eq-comparator 'foo 'bar 'baz))
             => (oset string-ci-comparator "foo" "bar" "baz")

Note that, when proc defines a mapping that is not 1:1, some of the mapped objects may be equivalent in the sense of comparator's equality predicate, and in this case duplicate elements are omitted as in the oset constructor. For example:

(oset-map (lambda (x) (quotient x 2))
          integer-comparator
          (oset integer-comparator 1 2 3 4 5))
 => (oset integer-comparator 0 1 2)

If the elements are the same in the sense of eqv?, it is unpredictable which one will be preserved in the result.

(oset-map/monotone proc comparator oset)

Equivalent to (oset-map proc comparator oset), but it is an error if proc does not induce a strictly monotone oset between the elements with respect to both the ordering of the comparator of oset and the ordering of comparator. Maybe be implemented more efficiently than oset-map.

(oset-for-each proc oset)

Applies proc to oset in order, discarding the returned values. Returns an unspecified result.

(oset-fold proc nil oset)

Invokes proc on each member of oset in order, passing the result of the previous invocation as a second argument. For the first invocation, nil is used as the second argument. Returns the result of the last invocation, or nil if there was no invocation.

(oset-fold/reverse proc nil oset)

Equivalent to (oset-fold proc nil oset) except that the elements are processed in reverse order.

(oset-filter predicate oset)

Returns an oset with the same comparator as oset, containing just the elements of oset that satisfy predicate.

(oset-remove predicate oset)

Returns an oset with the same comparator as oset, containing just the elements of oset that do not satisfy predicate.

(oset-partition predicate oset)

Returns two values: an oset with the same comparator as oset that contains just the elements of oset that satisfy predicate, and another oset, also with the same comparator, that contains just the elements of oset that do not satisfy predicate.

Conversion

(oset->list oset)

Returns a newly allocated list containing the members of oset in order.

(list->oset comparator list)

Returns an oset, created as if by oset using comparator, that contains the elements of list. Duplicate elements (in the sense of the equality predicate) are omitted.

(list->oset/ordered comparator list)

The same as list->oset, except that it is an error if the elements of list are not in order (in the sense of the comparator). May be implemented more efficiently than list->oset.

Subsets

None of these five predicates produces a total order on osets. In particular, oset=?, oset<?, and oset>? do not obey the trichotomy law.

(oset=? oset1 oset2 ...)

Returns #t if each oset contains the same elements.

Furthermore, it is explicitly not an error if oset=? is invoked on mappings that do not share the same comparator. In that case, #f is returned.

(oset<? oset1 oset2 ...)

Returns #t if each oset other than the last is a proper subset of the following oset, and #f otherwise.

(oset>? oset1 oset2 ...)

Returns #t if each oset other than the last is a proper superset of the following oset, and #f otherwise.

(oset<=? oset1 oset2 ...)

Returns #t if each oset other than the last is a subset of the following oset, and #f otherwise.

(oset>=? oset1 oset2 ...)

Returns #t if each oset other than the last is a superset of the following oset, and #f otherwise.

Set theoretic operations

(oset-union oset1 oset2 ...)
(oset-intersection oset1 oset2 ...)
(oset-difference oset1 oset2 ...)
(oset-xor oset1 oset2)

Return an oset that is the union, intersection, asymmetric difference, or symmetric difference of the osets. Asymmetric difference is extended to more than two osets by taking the difference between the first oset and the union of the others. Symmetric difference is not extended beyond two osets. Elements in the result oset are drawn from the first oset in which they appear. It is an error if not all element comparators are the same.

Single elements

(oset-min-element oset)

(oset-max-element oset)

Returns the least/greatest element contained in the oset oset. It is an error for oset to be empty.

(oset-element-predecessor oset obj failure)
(oset-element-successor oset obj failure)

Returns the element contained in the oset oset that immediately precedes/succeeds obj in the oset's order of elements. If no such element is contained in oset (because obj is the minimum/maximum element, or because oset is empty), returns the result of tail-calling the thunk failure.

Dividing osets

(oset-range= oset obj)
(oset-range< oset obj)
(oset-range> oset obj)
(oset-range<= oset obj)
(oset-range>= oset obj)

Returns an oset containing only the elements of the oset whose elements are equal to, less than, greater than, less than or equal to, or greater than or equal to obj (in the sense of the comparator of oset).

Note: Since elements in osets are unique, oset-range= returns an oset with at most one element.

(oset-split oset obj)

Returns five values equivalent to the results of invoking (oset-range< oset obj), (oset-range<= oset obj), (oset-range= oset obj), (oset-range>= oset obj), and (oset-range> oset obj), but may be more efficient.

(oset-catenate comparator oset1 element oset2)

Returns an oset using the comparator comparator whose elements are the union of the elements of the oset oset1, an oset containing only element, and the elements of oset2. It is an error if the elements contained in oset1 in their natural order, the element element, and the elements contained in oset2 in their natural order (in that order) do not form a strictly monotone sequence with respect to the ordering of comparator.

Implementation

The sample implementation is in the repository of this SRFI.

Acknowledgements

Thanks are due to the members of the SRFI 153 mailing list. In addition, without SRFI 146, by Arthur A. Gleckler and Marc Nieper-Wißkirchen, the implementation of this SRFI would have been much more difficult. Wolfgang Corcoran-Mathe found and fixed a large list of small bugs, without which this SRFI might never have been completed.

Copyright

© 2018, 2022, 2023 John Cowan.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler (originally Mike Sperber)