William D Clinger scripsit:

> SRFI 132 should not be allowed to go into final status until the problem
> noted below is fixed.

Thanks for the editorial heads-up.  I've found a lot of other editorial
problems and will be sending out a new draft as soon as I can.

> So long as I'm commenting on SRFI 132, let me state my opinion that its
> emphasis upon destructive operations is antiquated.  With generational
> garbage collectors, it's entirely possible that each of the destructive
> operations allocates a transaction record needed to preserve invariants
> that allow garbage to be collected without scanning the entire heap.

I've added a line to the effect that the big-oh guarantees apply only to
systems where car, cdr, set-car!, set-cdr!, vector-ref, and vector-set!
require O(1) time and space.

> If you examine the (srfi 132) library's definition, you will see it
> defines three procedures that should have been defined by the reference
> implementation but were not:
>
>     vector-find-median
>     vector-find-median!
>     vector-select!

They were not, of course, in Olin's code and _a fortiori_ not in the
Scheme48 version.  I had written but not yet posted the first two.
I appreciate all your efforts in that direction.

> By the way, the median element of a vector can be found in linear
> time, which is faster than the Ω(n lg n) worst-case performance
> mandated by the specification of vector-find-median! and strongly
> suggested by the specification of vector-find-median.  I assume a
> linear-time implementation of vector-find-median would not be
> ruled out by SRFI 132, so it might be a good idea to tell users
> of SRFI 132 that vector-find-median is likely to be faster than
> vector-find-median! for long vectors.

I will change the draft to say O(n) for find-median and O(n log n)
for find-median!, then.

> One conclusion I draw is that the number of distinct sorting
> routines specified by SRFI 132 cannot be justified on grounds
> of performance or efficiency.

If you mean "sorting routines" strictly, then there are only eight,
representing each of: list/vector, stable/unstable, pure/possibly-impure.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
Monday we watch-a Firefly's house, but he no come out.  He wasn't home.
Tuesday we go to the ball game, but he fool us.  He no show up.  Wednesday he
go to the ball game, and we fool him.  We no show up.  Thursday was a
double-header.  Nobody show up.  Friday it rained all day.  There was no ball
game, so we stayed home and we listened to it on-a the radio.  --Chicolini