We want to finalize SRFI 161 but haven't heard from you yet. Are you still looking for your original code? -- Marc P.S.: I hope that your eyesight has recovered. Am Mo., 7. Jan. 2019 um 12:26 Uhr schrieb elf <xxxxxx@ephemeral.net>: > > You are correct on this implementation. Let me find my original code before finalisation, please. > (Give me a few days as, as previously stated, i really cant see well right now.) > > -elf > > On January 7, 2019 11:13:01 AM UTC, "Marc Nieper-Wißkirchen" <xxxxxx@nieper-wisskirchen.de> wrote: >> >> >> >> Am Mo., 7. Jan. 2019 um 10:33 Uhr schrieb Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de>: >> > >> > 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? >> >> This wasn't a suitable counter-example. Here is one. The following program is supposed to display `#t'. However, it displays `#f': >> >> (import (scheme base) >> (scheme write)) >> >> (define (set-box! box val) (vector-set! box 0 val)) >> (define (unbox box) (vector-ref box 0)) >> (define box vector) >> >> (define (ubox val) (box (box (box val)))) >> (define (ubox-val box1) (unbox (unbox (unbox box1)))) >> (define (ubox-eq? box1 box2) (eq? (ubox-val box1) (ubox-val box2))) >> >> (define (unify box1 box2) >> (if (ubox-eq? box1 box2) >> box1 >> (let ((boxa (if (< (ubox-val box1) (ubox-val box2)) >> box1 >> box2)) >> (boxb (if (< (ubox-val box1) (ubox-val box2)) >> box2 >> box1))) >> (set-box! (unbox (unbox boxb)) (unbox (unbox (unbox boxa)))) >> (set-box! (unbox boxb) (unbox (unbox boxa))) >> (set-box! boxb (unbox boxa)) >> boxa))) >> >> (define box1 (ubox 1)) >> (define box2 (ubox 2)) >> (define box3 (ubox 3)) >> (define box4 (ubox 4)) >> (define box5 (ubox 5)) >> >> (unify box4 box5) >> (unify box3 box4) >> (unify box2 box3) >> (unify box1 box2) >> >> (display (ubox-eq? box4 box5)) >> (newline) >> >> -- Marc >> >> > >> > -- 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/ >> >> -- 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/
