Bug in SRFI-95 sample implementation of sorted? Sudarshan S Chawathe (07 Mar 2020 21:23 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
Arthur A. Gleckler
(07 Mar 2020 21:29 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
Aubrey Jaffer
(08 Mar 2020 00:17 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
Arthur A. Gleckler
(08 Mar 2020 00:29 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
John Cowan
(07 Mar 2020 22:30 UTC)
|
Bug in SRFI-95 sample implementation of sorted? Sudarshan S Chawathe 07 Mar 2020 21:22 UTC
There seems to be a bug in the SRFI-95 sample implementation of the sorted? procedure when given a vector argument with duplicates. The sample run below illustrates the problem and suggests a simple fix as well. (The sorted? procedure definition is verbatim from the sample implementation.) I apologize for the hackish definitions of some of the dependencies, but I don't think they change the behavior in the illustrated case. (I had some dependency trouble getting the official SLIB installed on my machine.) I believe this bug also exists in the current SLIB (slib-3b6). $ cat w.scm (import (scheme base) (scheme write)) (define array? vector?) (define array-ref vector-ref) (define (array-dimensions arr) (list (vector-length arr))) (define identity values) (define (sorted? seq less? . opt-key) (define key (if (null? opt-key) identity (car opt-key))) (cond ((null? seq) #t) ((array? seq) (let ((dimax (+ -1 (car (array-dimensions seq))))) (or (<= dimax 1) (let loop ((idx (+ -1 dimax)) (last (key (array-ref seq dimax)))) (or (negative? idx) (let ((nxt (key (array-ref seq idx)))) (and (less? nxt last) (loop (+ -1 idx) nxt)))))))) ((null? (cdr seq)) #t) (else (let loop ((last (key (car seq))) (next (cdr seq))) (or (null? next) (let ((nxt (key (car next)))) (and (not (less? nxt last)) (loop nxt (cdr next))))))))) (write (sorted? '(1 2 2 3) <)) (newline) (write (sorted? #(1 2 2 3) <)) (newline) $ chibi-scheme w.scm #t #f $ diff -u w.scm w2.scm --- w.scm 2020-03-07 16:02:00.395402293 -0500 +++ w2.scm 2020-03-07 16:02:00.395402293 -0500 @@ -20,7 +20,7 @@ (last (key (array-ref seq dimax)))) (or (negative? idx) (let ((nxt (key (array-ref seq idx)))) - (and (less? nxt last) + (and (not (less? last nxt last)) (loop (+ -1 idx) nxt)))))))) ((null? (cdr seq)) #t) (else $ chibi-scheme w2.scm #t #t $ Regards, -chaw