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/