I have forwarded your two other emails to the list. I hope that this
was your intent.

Am Mo., 7. Jan. 2019 um 08:14 Uhr schrieb Elf <xxxxxx@ephemeral.net>:
>
>
> Hello, question:
> Why is the equality predicate not stable?

This is by definition of the data structure. Newly created uboxes
aren't equal. After unification, they are. Here, equality is in the
sense of `ubox=?'.

> Please look at the attached code. This was a quick throw-together from
> my recollection of an implementation of disjoint sets I did several
> years ago (I didn't even start looking for the code yet), but a quick
> test showed that it has stable equality and no need for find, _provided_
> that the values being passed to ubox are orderable. (It should be
> possible to trivially modify it to not require this, but this is my
> recollection, as stated.)

I'm confused about the constant running time of your algorithm. See
Theorem 5 of this paper: https://dl.acm.org/citation.cfm?id=73040. It
gives a lower bound on the running time of an algorithm for a disjoint
set data structure, which is the bound the algorithm I implemented
achieves.

In fact, I am not convinced that your algorithm is correct if you have
more than three uboxes: Create four boxes x, y, z, w. Unify x and y.
Unify z and w. What happens when you unify y and z afterward?

-- Marc

P.S.: Get well soon!

>
> On Sun, 6 Jan 2019, Arthur A. Gleckler wrote:
>
> > Date: Sun, 6 Jan 2019 20:25:42
> > From: Arthur A. Gleckler <xxxxxx@speechcode.com>
> > To: xxxxxx@srfi.schemers.org
> > Subject: Last call for comments on SRFI 161: Unifiable Boxes
> >
> > Marc Nieper-Wißkirchen, author of SRFI 161, Unifiable Boxes, has asked me
> > to announce "last call" for this SRFI.  He believes that it is ready for
> > finalization, but would like to give reviewers one last chance to submit
> > corrections and feedback before we finalize it.
> >
> >  https://srfi.schemers.org/srfi-161
> >
> > In particular, I appeal to anyone reading this to try the sample
> > implementation, run the tests, and send feedback about your results.
> >
> > If you're interested in this SRFI, please give your feedback via the SRFI
> > 161 mailing list before 2019/1/14.  After that, assuming that no major
> > revisions are required, we will declare it final.
> >
> > Regards,
> >
> >
> > SRFI Editor
> >

--
Prof. Dr. Marc Nieper-Wißkirchen

Universität Augsburg
Institut für Mathematik
Universitätsstraße 14
86159 Augsburg

Tel: 0821/598-2146
Fax: 0821/598-2090

E-Mail: xxxxxx@math.uni-augsburg.de
Web: www.math.uni-augsburg.de/alg/mitarbeiter/mnieper/