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: [PATCH 2/3] Rewrite take-right, drop-right, drop-right! Date: Mon, 22 Sep 2014 20:40:27 +0200 Message-ID: <877g0vlcro.fsf@fencepost.gnu.org> References: <1401821778-19972-1-git-send-email-dak@gnu.org> <1401821778-19972-2-git-send-email-dak@gnu.org> <87k34yl4s3.fsf@yeeloong.lan> <87wq8ypblg.fsf@fencepost.gnu.org> <87fvfjk255.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1411411287 2622 80.91.229.3 (22 Sep 2014 18:41:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 22 Sep 2014 18:41:27 +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 Sep 22 20:41:20 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 1XW8Y3-0000oz-Ke for guile-bugs@m.gmane.org; Mon, 22 Sep 2014 20:41:19 +0200 Original-Received: from localhost ([::1]:48306 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XW8Y3-0007NI-8F for guile-bugs@m.gmane.org; Mon, 22 Sep 2014 14:41:19 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34942) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XW8Xw-0007Hg-Pl for bug-guile@gnu.org; Mon, 22 Sep 2014 14:41:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XW8Xs-00031V-Hf for bug-guile@gnu.org; Mon, 22 Sep 2014 14:41:12 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:57583) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XW8Xs-00030l-EM for bug-guile@gnu.org; Mon, 22 Sep 2014 14:41:08 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1XW8Xm-0008R4-KO for bug-guile@gnu.org; Mon, 22 Sep 2014 14:41:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 22 Sep 2014 18:41:02 +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.141141123732368 (code B ref 17485); Mon, 22 Sep 2014 18:41:02 +0000 Original-Received: (at 17485) by debbugs.gnu.org; 22 Sep 2014 18:40:37 +0000 Original-Received: from localhost ([127.0.0.1]:49146 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XW8XL-0008Pz-Uk for submit@debbugs.gnu.org; Mon, 22 Sep 2014 14:40:36 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:37346) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XW8XF-0008Pn-GF for 17485@debbugs.gnu.org; Mon, 22 Sep 2014 14:40:30 -0400 Original-Received: from localhost ([127.0.0.1]:44652 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XW8XE-0007ql-K7; Mon, 22 Sep 2014 14:40:29 -0400 Original-Received: by lola (Postfix, from userid 1000) id 6C2D7E620D; Mon, 22 Sep 2014 20:40:27 +0200 (CEST) In-Reply-To: <87fvfjk255.fsf@yeeloong.lan> (Mark H. Weaver's message of "Mon, 22 Sep 2014 13:15:18 -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:7574 Archived-At: Mark H Weaver writes: > David Kastrup writes: > >> Mark H Weaver 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