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-161@nospamsrfi.schemers.org`

. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

- Received: 2018/9/3
- Draft #1 published: 2018/9/6
- Draft #2 published: 2018/11/11
- Draft #3 published: 2019/1/8
- Finalized: 2019/2/8

Unifiable boxes are, like the boxes of SRFI 111, objects with a single mutable state. A constructor, predicate, accessor, and mutator are provided.

In addition to this, an equality predicate and union operations (link, union, unify) are provided. Applying a union operation to two unifiable boxes makes the two boxes equal (in the sense of the equality predicate). As a consequence, their state will also become identical. In the case of link and union, it will be the state of one of the two unioned boxes. In the case of unify, the state is determined by a supplied unification procedure.

Unifiable boxes are
also known under the names *disjoint-set data
structure*, *union–find data structure* or *merge–find
set*.

The disjoint-set (or union-find) forest is a basic, well-known data structure that tracks partitions of a set. For example, it can be used to keep track of the connected components of an undirected graph. It can also be used in implementations of unification or in implementing Kruskal's algorithm to find the minimum spanning tree of a graph.

The abstract data type defines the three
operations *make-set*, *find*,
and *union*. *Make-set* creates a singleton
set, *union* merges two sets, and *find* returns a
canonical representative of a set.

There are implementations of the union-find data structure in Haskell, SML/NJ, C++ (Boost), etc. It is the aim of this SRFI to provide an implementation for Scheme together with a standardized interface.

This SRFI defines the interface to a union-find data type with a SRFI 111 boxes-like interface. An implementation of this interface consists of operations for creating new unifiable boxes, getting the contents of a unifiable box, checking for equality of unifiable boxes, and for joining two unifiable boxes.

Unifiable boxes are analogous to boxes as expressed in the following table:

Operation | Boxes | Unifiable boxes |
---|---|---|

Constructor | `box` | `ubox` |

Predicate | `box?` | `ubox?` |

Accessor | `unbox` | `ubox-ref` |

Mutator | `set-box!` | `ubox-set!` |

Equality | `eq?` | `ubox=?` |

Union | n.a. | `ubox-unify!` , `ubox-union!` , `ubox-link!` |

* Note: Unifiable boxes use the standard naming pattern for
Scheme procedures. As SRFI 111 deviates (for historical reasons)
from this naming pattern, the naming patterns for boxes and for
unifiable boxes differ.
*

Using the procedures of this SRFI, the classical
operations *make-set*, *union*, and *find* can
be defined as follows:

(define (make-set x) (ubox x)) (define (union x y) (ubox-link! y x)) (define (find x) (ubox-ref x))

There is no comparator in the sense of SRFI 128 defined for unifiable boxes as the equality predicate for unifiable boxes is not stable.

*Unifiable boxes* form a new type as if created
by `define-record-type`

. The effect of using record-type
inspection or inheritance for the unifiable box type is unspecified.

*Equality* of unifiable boxes is an equivalence relation not
finer than `eqv?`

. The union
operations `ubox-unify!`

, `ubox-union!`

,
and `ubox-link!`

coarsen this equivalence relation.

Each unifiable box has a single mutable state, its *value*.
Equal unifiable boxes have the same state.

Each procedure below shall execute in (practically) constant time.
(The theoretical bound is *O(α(n))*, where *α*
is the inverse Ackermann function and *n* is the number of
unifiable boxes that are pairwise not `eq?`

to each other.)

It is an error if two threads access the same equivalence class of unifiable boxes at the same time. It is no error if two threads access distinct equivalence classes of unifiable boxes that remain distinct during the accesses at the same time.

`(ubox `

*value*)

Constructor. Returns a newly allocated unifiable box initialized
to

. The new unifiable box is not equal
to any previously constructed unifiable box.
*value*

`(ubox? `

*object*)

Predicate. Returns `#t`

if *object* is a unifiable
box, and `#f`

otherwise.

`(ubox-ref `

*ubox*)

Accessor. Returns the current value of the unifiable
box

.
*ubox*

`(ubox-set! `

*ubox* *value*)

Mutator. Changes the unifiable box

to hold
*ubox*

. The return value is unspecified.
*value*

`(ubox=? `

*ubox _{1}*

Equality predicate. Returns `#t`

if

are equal unifiable boxes,
and *ubox _{1}*
and

`#f`

otherwise.
`(ubox-unify! `

*proc* *ubox _{1}*

Union operation. Invokes

on the values
of *proc*

and *ubox _{1}*

*ubox*_{2}

,
makes *ubox*_{1}

and *ubox*_{2}

equal, and updates their
value to the result of the invocation of *proc*

.
The return value is unspecified.
`(ubox-union! `

*ubox _{1}*

Union operation. Makes the unifiable
boxes

and *ubox _{1}*

*ubox*_{2}

equal. The value of the
unified box is the value of
either *ubox*_{1}

or *ubox*_{2}

before the unification.
The return value is unspecified.
`(ubox-link! `

*ubox _{1}*

Union operation. Makes the unifiable
boxes

and *ubox _{1}*

*ubox*_{2}

equal. The value of the
unified box is the value of *ubox*_{2}

before the unification. The return value is unspecified.
The sample implementation comes in the form of the portable R7RS
library `(srfi 161)`

. It uses path compression and
union by rank.

Source for the sample implementation.

Disjoint-set forests were first described by Bernard A. Galler and
Michael J. Fischer in 1964 in their
paper *An improved
equivalence algorithm*.

The interface to a disjoint-set data structure that is described in
this SRFI has been modelled on
the `UREF`

signature of SML/NJ.

Olin Shivers has used the disjoint-set data structure, which is implemented by this SRFI, in Scheme code that generates random mazes. The code and the description of the algorithm is available on Olin Shiver's web site. Thanks to Arthur A. Gleckler for pointing this (practical) use of disjoint sets out to me.

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: Arthur A. Gleckler