bug-mit-scheme
[Top][All Lists]

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