[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-mit-scheme] lset-xor definition is wrong.
From: |
Chris Hanson |
Subject: |
Re: [Bug-mit-scheme] lset-xor definition is wrong. |
Date: |
Tue, 19 Jan 2010 19:10:18 -0800 |
Thanks; fixed in source.
On Tue, Jan 19, 2010 at 6:03 PM, Gerald Jay Sussman <address@hidden> wrote:
>
> ;;; In the src/runtime file srfi-1.scm the code is
>
> (define (lset-xor = . lists)
> (reduce (lambda (b a) ; Compute A xor B:
> ;; Note that this code relies on the constant-time
> ;; short-cuts provided by LSET-DIFF+INTERSECTION,
> ;; LSET-DIFFERENCE & APPEND to provide constant-time short
> ;; cuts for the cases A = (), B = (), and A eq? B. It takes
> ;; a careful case analysis to see it, but it's carefully
> ;; built in.
>
> ;; Compute a-b and a^b, then compute b-(a^b) and
> ;; cons it onto the front of a-b.
> (receive (a-b a-int-b) (lset-diff+intersection = a b)
> (cond ((null? a-b) (lset-difference b a =))
> ((null? a-int-b) (append b a))
> (else (fold (lambda (xb ans)
> (if (member xb a-int-b =) ans (cons xb ans)))
> a-b
> b)))))
> '() lists))
>
>
>
> ;;; It should be
>
> (define (lset-xor = . lists)
> (reduce (lambda (b a) ; Compute A xor B:
> ;; Note that this code relies on the constant-time
> ;; short-cuts provided by LSET-DIFF+INTERSECTION,
> ;; LSET-DIFFERENCE & APPEND to provide constant-time short
> ;; cuts for the cases A = (), B = (), and A eq? B. It takes
> ;; a careful case analysis to see it, but it's carefully
> ;; built in.
>
> ;; Compute a-b and a^b, then compute b-(a^b) and
> ;; cons it onto the front of a-b.
> (receive (a-b a-int-b) (lset-diff+intersection = a b)
> (cond ((null? a-b) (lset-difference = b a))
> ((null? a-int-b) (append b a))
> (else (fold (lambda (xb ans)
> (if (member xb a-int-b =) ans (cons xb ans)))
> a-b
> b)))))
> '() lists))
>
> ;;; the difference is (lset-difference = b a) --- the predicate is in the
> wrong position.
>
> ;;; An example the old thing gets wrong is (lset-xor eq? '(foo bar) '(foo
> bar))
>
>
>
> _______________________________________________
> Bug-MIT-Scheme mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/bug-mit-scheme
>