by John Cowan

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.

- Received: 2017-06-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~~- Returned to draft status: 2023-03-20
- Draft #5 published: 2023-03-20
- Draft #6 published: 2023-04-05
- Finalized: 2023-05-01

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

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

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

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.

Constructors:

`oset`

,`oset/ordered`

,`oset-unfold`

,`oset-unfold/ordered`

,`oset-accumulate`

Predicates:

`oset?`

,`oset-contains?`

,`oset-empty?`

,`oset-disjoint?`

Accessors:

`oset-member`

,`oset-element-comparator`

Updaters:

`oset-adjoin`

,`oset-adjoin/replace`

,`oset-delete`

,`oset-delete-all`

,`oset-pop`

,`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-remove`

,`oset-partition`

Conversion:

`oset->list`

,`list->oset`

,`list->oset/ordered`

Subsets:

`oset=?`

,`oset<?`

,`oset>?`

,`oset<=?`

,`oset>=?`

Set theoretic operations:

`oset-union`

,`oset-intersection`

,`oset-difference`

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

`(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 *seed*s. The procedure *proc* is applied to a
procedure *terminate* and the *seed*s, 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
```

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

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

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.

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

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

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

.

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 oset=? is invoked on mappings that do not share the same 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-intersection `

`)`

`(oset-difference `

`)`

`(oset-xor `

`)`

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.

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

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

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

`(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 sample implementation is in the repository of this SRFI.

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.

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