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/
