[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

neighbor deletion; param ordering; < & <=; fresh lists; cell recycling

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