---------- Forwarded message --------- From: Elf <xxxxxx@ephemeral.net> Date: Mo., 7. Jan. 2019 um 08:26 Uhr Subject: Re: Last call for comments on SRFI 161: Unifiable Boxes To: Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> I have a horrid eye infection at the moment so i can't see so clearly and i hit the wrong button, my apologies. As i recall, doing it the way you do ends up not being constant time. My first implementation was along similar lines, and i found that using a triple-layered pointer, essentially, with three mutations per unify, does work in constant time. No tracking of previous mutations required nor searching. Again, i haven't looked at this problem in some years, but i do remember this method (triple-pointer) not being something obvious nor standard nor discussed in the literature ... but it is fast :) To remove the ordering constraint isn't as obvious. i vaguelly recall thinking about it and deciding it wasnt worthwhile at the time, as it was a part of something fairly large and important and my data was always orderable. I suppose one could combine your method and my method, ie, every new box has an integer counter, and unify based on the counter value. I'm not sure the actual value will be correct, off the top of my head. -elf On Mon, 7 Jan 2019, Marc Nieper-Wißkirchen wrote: > Date: Sun, 6 Jan 2019 23:16:24 > From: Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> > To: Elf <xxxxxx@ephemeral.net> > Cc: Arthur A. Gleckler <xxxxxx@speechcode.com>, xxxxxx@srfi.schemers.org > Subject: Re: Last call for comments on SRFI 161: Unifiable Boxes > > Did you forget to attach your code to your email? > > Thanks, > > Marc > > Am Mo., 7. Jan. 2019 um 08:14 Uhr schrieb Elf <xxxxxx@ephemeral.net>: >> >> >> Hello, question: >> Why is the equality predicate not stable? >> >> 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 did not yet look at the sample implementation, apologies.) >> >> -elf >> >> 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/
