Re: [Ocaml-lib-devel] Idea with ExtList.fold_right

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

On Sat, 14 Jun 2003, John Max Skaller wrote:

> i don't want you counting my lists :-)

What is so evil about doing a List.length?  Especially in this case, where 
I hard cap the computational cost- as all I need to answer is if the 
length less than some constant.  So, for short lists (for some suitably 
wimbly definition of short) doing a list length is cheap.  For long lists, 
the length function short circuits out without doing a full count.  Maybe 
I should have made max smaller- 100 say, instead of 1000.  *Especially* 
since we're about to do an O(N) fold_right on the list anyways.

Now, mind you, there *are* reasons why my code may not be the most 
optimum.  Including:

- at some arbitrary point the algorithm trades off heap space for stack 
space, meaning it's hard to estimate how much of each you'll need.

- there is some performance benefit to be gained if you already know what 
the right routine to call is.

> 
> I know which routine I need from context often.
> So provide:
> 
> 	fold_right
> 	rev_fold_right

Or possibly even three- recursive, reversing, and sense-selecting.  

Brian