bug#17485: [PATCH 2/3] Rewrite take-right, drop-right, drop-right!

[David Kastrup <dak@gnu.org>]

Mark H Weaver <mhw@netris.org> writes:

> David Kastrup <dak@gnu.org> writes:
>
>> Mark H Weaver <mhw@netris.org> writes:
>>
>>> I can take care of doing this myself, and will of course still credit
>>> you in whatever manner you prefer, but I've run into a legal problem: we
>>> don't currently have copyright papers for you on file.  Are you willing
>>> to file copyright papers for GUILE?
>>
>> No problems with that.  Standard request-assign?
>
> request-assign.future would be good, which assigns "PAST AND FUTURE
> CHANGES".  Is that what you meant by "Standard request-assign"?
>
>> At any rate, here is what I would suggest to create: a function
>> min-length receiving a list of lists (possibly as separate arguments via
>> a rest argument).
>>
>> It will return the number of times one can do cdr on every of the given
>> arguments until at least one of them turns into a list end with nothing
>> turning into anything but a pair or a list end.
>
> I agree that these are reasonable semantics for validation by 'map' and
> 'for-each'.  I went ahead and implemented it (attached below).  For
> efficiency in the common case, I check for cycles in only one list at a
> time.  If a cycle is found, the circular list is discarded and cycle
> detection begins on another list.  Let me know if you see a way to
> improve it.

Don't walk the lists in synch.  That's the worst possible way to do
stuff regarding memory locality.

Instead do the lists one by one.  Keep in mind the length of the
shortest list so far and whether any list of that length was improper.
Once you walked the length of the shortest list so far, you can abort
the current list.  Since cyclical lists will tend to be very short (and
not uncommon for the multiple-list case), I'd probably let the tortoise
run even when it is known that there is already one finite list.

Walking the lists in synch is only an advantage when there are several
finite lists and later ones are considerably shorter than preceding
ones.  Not a likely use case.

The work horse would be something like "limited-length" which gets a
list and a previous limit, where #f means "no limit and/or circular",
2*n is used for proper lists and 2*n-1 for improper lists (in order to
dominate the minimum in the case of equal lengths of proper and improper
lists).

The first idea was to use n and n-1/2, but since length comparisons are
done for every element, 2n and 2n-1 should be cheaper.

If the minimum after the last list is odd, flag an error, else divide by
2 and return the result.

-- 
David Kastrup