This page is part of the web mail archives of SRFI 32 from before July 7th, 2015. The new archives for SRFI 32 contain all messages, not just those from before July 7th, 2015.
I've just read through the SRFI-32 draft and scanned the archive of the email discussion list. Great review, Steck. Thank you very much! Maybe I'm near-sighted, but where is the reference implementation? David Feuer asked the same question on the discussion list, and I didn't see a response. I think I responded. I haven't released the ref implementation. I still need to clean up one of the routines, and I have been putting my SRFI time into the discussion & spec. - "an SRFI" -> "a SRFI" (? depends on how you pronounce "SRFI" :-)) - in the snippet of code that follows "The definition is rather different, given a <= comparator:", you should transpose `x' and `y' for one of the arguments to `and' - in the section on types of parameters and return values, it uses the word "unspecified"; in the descriptions of procedures, this mutates to "unspecific" - `list-merge!' is described as "iterative, not recursive". Hmmm, that's a bit confusing to me -- I'd just write "iterative". All fixed. - under `sort-lib', in the type for `vector-delete-neighbor-dups!', the return value is named end'. Hmmm, I'd avoid using a quote there, and name it end2. This name is used a couple of other places, I think. I kinda like END'. - in the description of START and END, `v' is lower-case in (vector-length v), then upper-case in `where V ...'. But this text may be redundant, since the same setup is already described in the section "All vector operations accept optional subrange parameters". - there is a general inconsistency in the capitalization of procedure names, or maybe I don't understand why they're in upper-case in certain places, and lower-case in others I need to make a pass to make capitalisation consistent. - in the type for `vector-merge!', the first optional argument is given as `start', but later mentioned as `START0' (inconsistent capitalization? as well as the `0') I replaced START0/END0 with START/END uniformly. - I don't understand the comment on "Pure list merge sort" that begins "and possibly better ..." and what the "above" refers to. I changed "better" to "O(n)," producing Stable and fast -- O(n lg n) worst-case, and possibly O(n), depending upon the input list (see above). "Above" means the three paragraphs *immediately above*. - it's stated that the `LIST-SORTED?' function *will* return false given a <= comparator and a list with adjacent equal elements. I think that depends on the semantics of `LIST-SORTED?' (the intended semantics is described later in the SRFI). Maybe "may" is a better word choice here, before the reader has seen that semantics. No, the semantics is fixed, so "may" isn't the right word. It *will*. Maybe I should reorder the text. - after a lengthy discussion of why < is better than <=, there's a reference to Common Lisp's similar choice. I'd put that before your own explanation, and say something like "While I don't know CL's reasons for that choice, here are my own." I don't really *have* any good reasons for using <, other than it is the common practice. That section *doesn't* say one is better than the other, just that they are quite different, and what the implications of that difference are. - `vector-delete-neighbor-dups{!}' is described twice, as part of sortlib and delndup-lib. Also, the description that it implements a linear-time algorithm appears twice (well, the second time, that also applies to the list deletion procedures). Yeah, I know, and you are correct to push me to do something about this redundancy. I will reflect on this. A more substantive comment: - I don't understand why there are four vector sort libraries. Presumably, there's not a lot of code there. Couldn't they go into just one library? I don't see why you should have to link in six different sort libraries just to get heapsort. On the order of arguments issue: I'd be in favor of putting the procedure argument in front of list/vector data, uniformly. If this SRFI is widely-adopted, most of the procedure names will be new in most implementations. So you may as well do the right thing now, rather than have to live with a bad decision for years to come. It also helps to distinguish Scheme from C, whose quicksort() puts the comparator last. :-) This seems to be the consensus, to my pleasant surprise. I'm waiting to hear from a few more implementors. I hope you find these comments useful. Very. Thanks. May I forward your msg to the SRFI mailing list / archive? -Olin