Re: [Caml-list] tree walking with... specular rec functions? what else?

[Michal Moskal <malekith@pld-linux.org>]

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