bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9

[David Kastrup]

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