Re: [Ocaml-lib-devel] De-functor-ized Psqueue

[Brian H. <bri...@ql...>]

On Tue, 27 May 2003, Nicolas Cannasse wrote:

> > Now consider rewritting this to take an Enum instead of a list.  You have
> > to force the algorithm into fold somehow- which means managing a
> > handrolled stack (the above code is double non-tail recursive).
> 
> Since you're building a tree you don't need to be tail rec ( the stack will
> grow in O(log n) ! )

Yeah.  Building a stack isn't the problem- in fact, I have to do that for 
tree_to_enum.  It's the complexity of the stack.  

> 
> > For sheer code clarity, I think 'a option is a cleaner response than
> > throwing an exception.
> 
> I don't agree here :
> - BUT the internal next is most of the time "concatening" the next functions
> in a purely functional way, so for example after two Enum.maps and doing an
> Enum.iter, you'll have to check the None/Some three times ! 

For Enum.iter this is correct.  However, for doing just about anything 
else you need to try/catch the exception the same number of times you need 
to check for None/Some.  And I would expect map and fold to be at least as 
important as iter.

In both cases the expected case is for it not to be the end of the 
enumeration- for the exception not to be thrown, or for Some x to be 
returned.  I don't know how expensive setting up a try/catch block is, but 
since the branch between None/Some is a highly predictable branch, the 
cost of the branch is 1 clock cycle *or less*.  Add another clock cycle 
for the memory load (from L1 cache- the word was just allocated and 
filled).  Below the level that would be measurable in any real-world case, 
would be my guess.  In either case, I think this is a premature 
optimization.

Plus there is the problem of having the exported next behaving differently 
from the imported next- a likely source of confusion.

Brian