Title

Ordered sets

Author

John Cowan

Status

This SRFI is currently in withdrawn 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 collections that can contain any Scheme objects, provided that 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.

Issues

None at present.

Rationale

The sets of SRFI 113 may depend on either an ordering predicate or a hash function. The sets provided here are always ordered.

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.

Specification

Osets are mutually disjoint, and 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 a oset.

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

It is an error to add or remove an object for a 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.

Linear update

The procedures of this SRFI, by default, are "pure functional" -- they do not alter their parameters. However, this SRFI also defines "linear-update" procedures, all of whose names end in !. They have hybrid pure-functional/side-effecting semantics: they are allowed, but not required, to side-effect one of their parameters in order to construct their result. An implementation may legally implement these procedures as pure, side-effect-free functions, or it may implement them using side effects, depending upon the details of what is the most efficient or simple to implement in terms of the underlying representation.

It is an error to rely upon these procedures working by side effect. so clients of these procedures write in a functional style, but must additionally be sure that, when the procedure is called, there are no other live pointers to the potentially-modified oset (hence the term "linear update").

There are two benefits to this convention:

In practice, these procedures are most useful for efficiently constructing osets in a side-effecting manner, in some limited local context, before passing the oset outside the local construction scope to be used in a functional manner.

Scheme provides no assistance in checking the linearity of the potentially side-effected parameters passed to these functions -- there's no linear type checker or run-time mechanism for detecting violations.

Note that if an implementation uses no side effects at all, it is allowed to return existing osets rather than newly allocated ones, even where this SRFI explicitly says otherwise.

Procedures whose names end in ! have the same behavior as the corresponding procedures whose names don't have !, except for being linear-update in their (first) oset argument rather than pure functional. This is mentioned here once and for all.

Procedure index

Oset procedures

Constructors

(oset comparator element ... )

(oset/ordered 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. The oset/ordered procedure is the same as oset except that it is an error if the elements are out of order or duplicated. It may be more efficient.

(oset-unfold stop? mapper successor seed comparator)

(oset-unfold/ordered 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. The oset-unfold/ordered procedure is the same as oset-unfold except that it is an error if the elements are out of order or duplicated. It may be more efficient.

Predicates

(oset? obj)

Returns #t if obj is a 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 ...)

(oset-adjoin! oset element ...)

The oset-adjoin procedure returns an oset that uses the same comparator as oset and contains all the values of oset, and in addition each element unless it is already equal (in the sense of the comparator) to one of the existing or newly added members. It is an error to add an element to oset that does not return #t when passed to the type test procedure of the comparator.

(oset-replace oset element)

(oset-replace! oset element)

The oset-replace procedure returns an oset that uses the same comparator as oset and contains all the values of oset except as follows: If element is equal (in the sense of oset's comparator) to an existing member of oset, then that member is omitted and replaced by element. If there is no such element in oset, then oset is returned unchanged.

(oset-delete oset element ...)

(oset-delete! oset element ...)

(oset-delete-all oset element-list)

(oset-delete-all! oset element-list)

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.

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 ])

(oset-pop! oset [ failure ])

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

The oset-pop procedure chooses the smallest 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 oset-pop/reverse procedure is the same as oset-pop except that it chooses the largest element.

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 failure with no arguments 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 associations are processed in reverse order with respect to the natural ordering of the elements.

(oset-filter predicate oset)

(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)

(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)

(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.

Copying and conversion

(oset-copy oset)

Returns an oset containing the elements of oset, and using the same comparator.

(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.

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 mapping=? is invoked on mappings that do not share the same (key) 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 theory operations

(oset-union oset1 oset2 ...)

(oset-union! oset1 oset2 ...)

(oset-intersection oset1 oset2 ...)

(oset-intersection! oset1 oset2 ...)

(oset-difference oset1 oset2 ...)

(oset-difference! oset1 oset2 ...)

(oset-xor 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.

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 a 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.

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)

(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.

Comparator

The following comparator is used to compare osets, and allow osets of osets, hash tables of osets, etc.

oset-comparator

Note that this comparator does not provide ordering predicates, as there is no ordering between osets. It is an error to compare osets with different element comparators. Oset-comparator is registered with SRFI 128's default comparator.

Implementation

An unfinished sample implementation is in the repository of this SRFI.

Copyright

Copyright (C) John Cowan 2018. All Rights Reserved.

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 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: Mike Sperber