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.
David- Thanks for the review! From: David Feuer <dfeuer@xxxxxxxxxxxxx> Subject: neighbor deletion Why does this belong in a sorting SRFI? Good question -- it ain't sorting. But it's something you typically do with sorted data. I considered punting these. But writing them well takes a little work (especially the iterative destructive list version), and part of the library game, for me, is that I make an effort and write a thing well, once, and then everyone can use it. Count it under "manipulation of sorted data," just like vector binary search. I think the ordering op should go first. Me, too. But the compatibility win outweighs my preference here. Also, <= seems much more intuitive than <. Me, too. But it busts compatibility with just about *everything* out there, lisp and Scheme. I don't think it's worth it. Can anyone find out why Common Lisp settled on <? (I have emailed Kent Pitman asking him.) I note that the non-mutating vector sorts are guaranteed to copy the vector. It would seem potentially very useful to give some indication of whether the new vector is in fact different from the old vector, to allow programmers to optimize for generational collectors. Heh? The new vector is *guaranteed* to be different from the old vector. You alter one, the other is unchanged. Guaranteed. It would seem potentially slightly useful to have "fully copying" sorts, that are guaranteed not to mutate the original list and not to share any list structure with it, but I don't know if this would be sufficiently useful to include. If you are in a functional mood, then you ought to be OK with sharing structure -- all I really should have to promise you is that I won't frob your input list. This is SORT-LIST's contract: it does not alter its input, but is allowed to share structure. If you really, really need to know that the returned list is fresh, that it contains no cons cells in common with the input list, you are in a side-effecting world. Otherwise you would not care about cons-cell identity, right? So copy the list and then use SORT-LIST!. It would probably run faster and certainly allocate less "trash" memory than a purely functional sort. So we might as well let this one slide. make only a single, iterative, linear-time pass over their argument lists, constructing their results by side-effecting these lists. The intent of this algorithmic commitment is to allow the programmer to be sure that if, for example, LIST-MERGE! is asked to merge two ten-million-element lists, the operation will complete without performing some extremely (possibly twenty-million) deep recursion. That is, LIST-MERGE! is implemented as an iterative algorithm. " So does this mean that LIST-MERGE! is guaranteed to return an object containing no new cons cells? The spec is not so clear here. In the Republican expression, "Read my lips: no new cells." Yeah, that's what I meant to say. Or, let me be a bit more careful. LIST-MERGE! is not simply *allowed* to recycle its list inputs, it is *required* to recycle them. I suppose this means that a perverse implementation could gratuitously allocate cells on the side, but every cell in the input has to show up in the output, so there are not going to be any new cells in the answer. Let me add a little bit of language to the spec to spell this out more (which is mostly taken from the later appearance of LIST-MERGE!): These procedures use SET-CDR!s to rearrange the cells of the lists into the final result. As such, they do not allocate any extra cons cells -- they work "in place." Hence, any cons cell appearing in the result must have originally appeared in an input. How's that? -Olin