SRFI 161: Unifiable Boxes

by Marc Nieper-Wißkirchen

status: final (2019-02-08)

keywords: Data Structure

• The SRFI Document
• Discussion Archive
• Git repo (on Github)
• srfi-161@nospamsrfi.schemers.org (subscribers only)
• Subscribe to srfi-161 mailing list

  daily digest?

• Unsubscribe from srfi-161 mailing list

Abstract

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.