From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 Date: Mon, 02 Jun 2014 09:59:28 +0200 Message-ID: <87wqczagin.fsf@fencepost.gnu.org> References: <87y4y6t0or.fsf@fencepost.gnu.org> <87r4382o5m.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1401696021 13272 80.91.229.3 (2 Jun 2014 08:00:21 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 2 Jun 2014 08:00:21 +0000 (UTC) Cc: 17485@debbugs.gnu.org To: Mark H Weaver Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Mon Jun 02 10:00:13 2014 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WrNAC-000288-Pj for guile-bugs@m.gmane.org; Mon, 02 Jun 2014 10:00:12 +0200 Original-Received: from localhost ([::1]:43522 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WrNAC-0006bF-CL for guile-bugs@m.gmane.org; Mon, 02 Jun 2014 04:00:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49298) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WrNA8-0006Xu-Vu for bug-guile@gnu.org; Mon, 02 Jun 2014 04:00:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WrNA4-0004UF-U9 for bug-guile@gnu.org; Mon, 02 Jun 2014 04:00:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:41385) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WrNA4-0004TU-QX for bug-guile@gnu.org; Mon, 02 Jun 2014 04:00:04 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WrNA4-0006xL-BF for bug-guile@gnu.org; Mon, 02 Jun 2014 04:00:04 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 02 Jun 2014 08:00:04 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17485 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 17485-submit@debbugs.gnu.org id=B17485.140169598326676 (code B ref 17485); Mon, 02 Jun 2014 08:00:04 +0000 Original-Received: (at 17485) by debbugs.gnu.org; 2 Jun 2014 07:59:43 +0000 Original-Received: from localhost ([127.0.0.1]:40262 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WrN9i-0006wC-W3 for submit@debbugs.gnu.org; Mon, 02 Jun 2014 03:59:43 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:41749 ident=Debian-exim) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WrN9g-0006w3-5Z for 17485@debbugs.gnu.org; Mon, 02 Jun 2014 03:59:41 -0400 Original-Received: from localhost ([127.0.0.1]:49050 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WrN9e-0006tf-Sp; Mon, 02 Jun 2014 03:59:39 -0400 Original-Received: by lola (Postfix, from userid 1000) id DFC2AE05F5; Mon, 2 Jun 2014 09:59:28 +0200 (CEST) In-Reply-To: <87r4382o5m.fsf@yeeloong.lan> (Mark H. Weaver's message of "Sun, 01 Jun 2014 19:41:41 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7477 Archived-At: Mark H Weaver writes: > David Kastrup 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 . > > 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