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/