From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA21950; Mon, 12 May 2003 15:36:17 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA21905 for ; Mon, 12 May 2003 15:36:16 +0200 (MET DST) Received: from ep09.kernel.pl (ep09.kernel.pl [212.87.11.162]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h4CDaDH23433 for ; Mon, 12 May 2003 15:36:13 +0200 (MET DST) Received: (qmail 29563 invoked by uid 566); 12 May 2003 13:36:08 -0000 Date: Mon, 12 May 2003 15:35:42 +0200 From: Michal Moskal To: John Carr Cc: Brian Hurt , caml-list@inria.fr Subject: Re: [Caml-list] tree walking with... specular rec functions? what else? Message-ID: <20030512133542.GA9977@roke.freak> References: <200305121257.IAA29080@nerd-xing.mit.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200305121257.IAA29080@nerd-xing.mit.edu> User-Agent: Mutt/1.4.1i X-PGP-Fingerprint: CF89 1B14 11BE 1CC9 2CA3 7497 5E32 69B4 BC71 B4C2 X-AntiVirus: scanned for viruses by AMaViS 0.2.1 (http://amavis.org/) X-Spam: no; 0.00; michal:01 moskal:01 malekith:01 pld-linux:01 caml-list:01 0400,:01 non-mutable:01 wroclaw:01 kernel:01 rec:01 imply:02 inner:02 tree:02 gcs:03 wrote:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, May 12, 2003 at 08:57:05AM -0400, John Carr wrote: > > I have a minor comment unrelated to the basic algorithm. > > > ... > > let rec outer lst = > > if (List.length lst) == 0 then () > > else outer (inner lst []) > > in > > ... > > In general it is better to test for empty rather than compare the size > of a collection to 0. With some collections (including lists) testing > for empty takes constant time but computing size takes linear time. > > Instead of > > if (List.length lst) == 0 then empty-code else full-code > > either of these will be faster: > > if lst == [] then empty-code else full-code On non-mutable structures, the behavior of (==) is implementation-dependent. Which means that lst = [] does not imply lst == []. In other words, one should use: if lst = [] then empty-code else full-code or pattern matching, as you said. -- : Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv : PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners