[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9
From: |
David Kastrup |
Subject: |
bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 |
Date: |
Mon, 02 Jun 2014 09:59:28 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) |
Mark H Weaver <address@hidden> writes:
> David Kastrup <address@hidden> writes:
>
>> For all the cleverness involved here, one has to run through the whole
>> list anyway. It makes no real sense to do this in this manner. The
>> motivation may be to have a warm cache when k is small, but the result
>> is self-defeating because of VM stack buildup.
>>
>> (define (drop-right lis k)
>> (drop lis (- (length lis) k)))
>>
>> should be all that is needed.
>
> That won't be sufficient. SRFI-1 specifies that 'drop-right' works
> for dotted lists, i.e. finite non-nil-terminated lists, whereas
> 'length' accepts only proper lists.
Yes, I noticed.
> It includes these examples:
>
> (drop-right '(1 2 3 . d) 2) => (1)
> (drop-right '(1 2 3 . d) 0) => (1 2 3)
>
> See <http://srfi.schemers.org/srfi-1/srfi-1.html>.
>
> Would you like to propose another fix?
The simplest fix would be using length+ rather than length, but that
would require length+ to return the length of dotted lists (defined as
its spine) rather than #f. As I interpret the standard, length+ for
dotted lists is unspecified. It now returns #f. Other options would be
throwing an error, delivering the length of the spine, or returning the
negative of the total number of elements (meaning that the "dotted list"
5 has a length+ of -1, distinguishable from (length+ '())).
Since it is suggested in srfi-1 that many routines do something useful
when given dotted lists, it's rather inconvenient that there is _no_
list length operator working on dotted lists. There are routines that
use length+ as a building block in order to admit circular lists and
they tend to fail with surprising error messages when given dotted
lists.
So I lean towards making length+ put out the spine length of dotted
lists, obviously requiring a review of its few uses. Having yet another
length operator, in contrast, seems like overkill. While a "arithmetic
if" style operator yanking out negative values for dotted lists would
have the advantage of delivering complete information, its usage would,
well, be awkward. And in explicit recursion/loops, one will eventually
arrive at the end of the processed list and will see whether the first
non-pair is '() or not without additional cost.
--
David Kastrup