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.

- Received: 2017-06-27
- 60-day deadline: 2017-08-27
- Draft #1 published: 2017-06-28
- Draft #2 published: 2017-07-15
- Draft #3 published: 2018-03-06
- Draft #4 published: 2018-07-08
- Withdrawn: 2018-07-08

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

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.

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.

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:

Implementations are free to provide the most efficient possible implementation, either functional or side-effecting.

Programmers may nonetheless continue to assume that osets are purely functional data structures: they may be reliably shared without needing to be copied, uniquified, and so forth.

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.

Constructors:

`oset`

,`oset/ordered`

,`oset-unfold`

,`oset-unfold/ordered`

Predicates:

`oset?`

,`oset-contains?`

,`oset-empty?`

,`oset-disjoint?`

Accessors:

`oset-member`

,`oset-element-comparator`

Updaters:

`oset-adjoin`

,`oset-adjoin!`

,`oset-replace`

,`oset-replace`

,`oset-delete`

,`oset-delete!`

,`oset-delete-all`

,`oset-delete-all!`

,`oset-pop`

,`oset-pop!`

,`oset-pop/reverse`

,`oset-pop!/reverse`

The whole oset:

`oset-size`

,`oset-find`

,`oset-count`

,`oset-any?`

,`oset-every?`

Mapping and folding:

`oset-map`

,`oset-map/monotone`

,`oset-for-each`

,`oset-fold`

,`oset-fold/reverse`

,`oset-filter`

,`oset-filter!`

,`oset-remove`

,`oset-remove!`

,`oset-partition`

,`oset-partition!`

Copying and conversion:

`oset-copy`

,`oset->list`

,`list->oset`

Subsets:

`oset=?`

,`oset<?`

,`oset>?`

,`oset<=?`

,`oset>=?`

Set theory operations:

`oset-union`

,`oset-union!`

,`oset-intersection`

,`oset-intersection!`

,`oset-difference`

,`oset-difference!`

,`oset-xor`

,`oset-xor!`

Single elements:

`oset-min-element`

,`oset-max-element`

,`oset-element-predecessor`

,`oset-element-successor`

Dividing osets:

`oset-range=`

,`oset-range<`

,`oset-range>`

,`oset-range<=`

,`oset-range>=`

,`oset-split`

,`oset-catenate`

Comparator:

`oset-comparator`

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

`(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? `

*oset _{1} oset_{2}*

`)`

Returns `#t`

if *oset _{1}* and

`#f`

otherwise.`(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*.

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

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

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

,
but it is an error if *proc* *comparator* *oset*)*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 `

except that the associations are processed in reverse order with
respect to the natural ordering of the elements.
*proc* *nil* *oset*)

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

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

None of these five predicates produces a total order on osets. In particular, `oset=?`

, `oset<?`

, and `oset>?`

do not obey the trichotomy law.

`(oset=? `

*oset _{1} oset_{2}* ...

`)`

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<? `

*oset _{1} oset_{2}* ...

`)`

Returns `#t`

if each *oset* other than the last is a proper subset of the following *oset*, and `#f`

otherwise.

`(oset>? `

*oset _{1} oset_{2}* ...

`)`

Returns `#t`

if each *oset* other than the last is a proper superset of the following *oset*, and `#f`

otherwise.

`(oset<=? `

*oset _{1} oset_{2}* ...

`)`

Returns `#t`

if each *oset* other than the last is a subset of the following *oset*, and `#f`

otherwise.

`(oset>=? `

*oset _{1} oset_{2}* ...

`)`

Returns `#t`

if each *oset* other than the last is a superset of the following *oset*, and `#f`

otherwise.

`(oset-union `

*oset _{1} oset_{2}* ...

`)`

`(oset-union! `

*oset _{1} oset_{2}* ...

`)`

`(oset-intersection `

*oset _{1} oset_{2}* ...

`)`

`(oset-intersection! `

*oset _{1} oset_{2}* ...

`)`

`(oset-difference `

*oset _{1} oset_{2}* ...

`)`

`(oset-difference! `

*oset _{1} oset_{2}* ...

`)`

`(oset-xor `

*oset _{1} oset_{2}*

`)`

`(oset-xor! `

*oset _{1} oset_{2}*

`)`

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.

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

`(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>= `

,
and
*oset* *obj*)`(oset-range> `

, but
may be more efficient.
*oset* *obj*)

`(oset-catenate comparator `

*oset*_{1} *element*
*oset*2)

`(oset-catenate! comparator `

*oset*_{1} *element*
*oset*2)

Returns an oset using the
comparator *comparator* whose elements
are the union of the elements of the
oset *oset*_{1},
an oset containing only *element*,
and the elements of *oset*_{2}. It is an error if the elements
contained in *oset*_{1} in their
natural order, the element *element*, and the elements contained
in *oset*_{2} in their natural order
(in that order) do not form a strictly monotone sequence with respect
to the ordering of *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.

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

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