From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Bob Rogers Newsgroups: gmane.emacs.devel Subject: Re: To be a list or not Date: Sat, 29 Dec 2007 22:52:04 -0500 Message-ID: <18295.5604.556472.248446@rgrjr.rgrjr.com> References: <477568AC.7090304@gmail.com> <18293.28417.122146.27016@kahikatea.snap.net.nz> <47758120.5000507@gmail.com> <18293.35504.41211.784522@kahikatea.snap.net.nz> <4775925A.6020300@gmail.com> <18293.49293.672805.512265@rgrjr.rgrjr.com> <87odc96waz.fsf@uwakimon.sk.tsukuba.ac.jp> <87abnt6lym.fsf@uwakimon.sk.tsukuba.ac.jp> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1198986774 20442 80.91.229.12 (30 Dec 2007 03:52:54 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 30 Dec 2007 03:52:54 +0000 (UTC) Cc: Tom Tromey , "Lennart Borgman \(gmail\)" , Emacs Devel To: "Stephen J. Turnbull" Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 30 04:53:07 2007 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1J8pEY-0006W6-Dm for ged-emacs-devel@m.gmane.org; Sun, 30 Dec 2007 04:53:06 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1J8pED-0002yt-5U for ged-emacs-devel@m.gmane.org; Sat, 29 Dec 2007 22:52:45 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1J8pDe-0002IQ-P8 for emacs-devel@gnu.org; Sat, 29 Dec 2007 22:52:11 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1J8pDb-0002CX-0R for emacs-devel@gnu.org; Sat, 29 Dec 2007 22:52:09 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1J8pDa-0002C6-7Y for emacs-devel@gnu.org; Sat, 29 Dec 2007 22:52:06 -0500 Original-Received: from c-24-128-232-192.hsd1.ma.comcast.net ([24.128.232.192] helo=rgrjr.dyndns.org) by monty-python.gnu.org with smtp (Exim 4.60) (envelope-from ) id 1J8pDZ-0007h8-Nc for emacs-devel@gnu.org; Sat, 29 Dec 2007 22:52:05 -0500 Original-Received: (qmail 12988 invoked by uid 500); 30 Dec 2007 03:52:04 -0000 In-Reply-To: <87abnt6lym.fsf@uwakimon.sk.tsukuba.ac.jp> X-Mailer: VM 7.19 under Emacs 23.0.50.1 X-detected-kernel: by monty-python.gnu.org: Linux 2.4-2.6 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:85662 Archived-At: From: "Stephen J. Turnbull" Date: Sun, 30 Dec 2007 09:54:41 +0900 Tom Tromey writes: > >>>>> "Stephen" == Stephen J Turnbull writes: > > Stephen> But please call it `true-list-p', which is the name of the > Stephen> similar XEmacs built-in. > > Here's one stab at it. This is basically lifted from safe-length. Looks very familiar. XEmacs implements one change you might think about. Specifically, it delays starting the tortoise until the length is "long enough to suspect circularity". I don't know if the value chosen was tuned or not. As I understand it, this makes the function slightly faster for shorter lists, slightly slows down longer true lists, and might double the detection time for cyclical lists. Looks like a win to me, but YMMV. Another trick is to unroll the loop so that it follows the tortoise, as done in the CMU Common Lisp list-length function shown below (which is in the public domain). If you combine both tricks, you would have two loops, the first of which only needs to maintain a tail and a counter, and the second only needs to maintain a tail and a tortoise. But it's not at all clear that this is worth all that trouble . . . -- Bob ------------------------------------------------------------------------ (defun list-length (list) "Returns the length of the given List, or Nil if the List is circular." (do ((n 0 (+ n 2)) (y list (cddr y)) (z list (cdr z))) (()) (declare (fixnum n) (list y z)) (when (endp y) (return n)) (when (endp (cdr y)) (return (+ n 1))) (when (and (eq y z) (> n 0)) (return nil))))