From: David Kastrup <dak@gnu.org>
To: Mark H Weaver <mhw@netris.org>
Cc: 17485@debbugs.gnu.org
Subject: bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9
Date: Mon, 02 Jun 2014 09:59:28 +0200 [thread overview]
Message-ID: <87wqczagin.fsf@fencepost.gnu.org> (raw)
In-Reply-To: <87r4382o5m.fsf@yeeloong.lan> (Mark H. Weaver's message of "Sun, 01 Jun 2014 19:41:41 -0400")
Mark H Weaver <mhw@netris.org> writes:
> David Kastrup <dak@gnu.org> 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
next prev parent reply other threads:[~2014-06-02 7:59 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-05-13 10:47 bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 David Kastrup
2014-06-01 23:41 ` Mark H Weaver
2014-06-02 7:59 ` David Kastrup [this message]
2014-06-03 18:56 ` bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f David Kastrup
2014-06-03 18:56 ` bug#17485: [PATCH 2/3] Rewrite take-right, drop-right, drop-right! David Kastrup
2014-06-04 3:29 ` Mark H Weaver
2014-06-04 3:45 ` Mark H Weaver
2014-09-20 14:56 ` Mark H Weaver
2014-09-20 15:15 ` David Kastrup
2014-09-22 17:15 ` Mark H Weaver
2014-09-22 18:40 ` David Kastrup
2014-06-03 18:56 ` bug#17485: [PATCH 3/3] Reimplement reduce-right in srfi-1 David Kastrup
2014-06-04 3:30 ` Mark H Weaver
2014-06-04 3:42 ` bug#17485: [PATCH 1/3] Let length+ return the length of dotted lists rather than #f Mark H Weaver
2014-06-04 4:57 ` David Kastrup
2014-06-04 10:09 ` David Kastrup
2014-06-05 13:57 ` David Kastrup
2016-06-21 14:42 ` bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 Andy Wingo
2016-06-21 15:31 ` David Kastrup
2016-07-12 7:07 ` Andy Wingo
2016-07-12 7:43 ` bug#17485: Ugh, well David Kastrup
2016-07-12 13:54 ` Andy Wingo
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87wqczagin.fsf@fencepost.gnu.org \
--to=dak@gnu.org \
--cc=17485@debbugs.gnu.org \
--cc=mhw@netris.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).