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

[Nicolas C. <war...@fr...>]

> So do a length of the list and pick the "right" algorithm for the job.
> The length should be limited- once we know the list is too long, we can
> exit (we don't need the full length).  This gives rise to the following
> code:
[...]
> Thoughts?  Comments?  Benchmarks?

The problem here is that the "good number" will be good for some
applications but not good for other ones.
For example if one of my program have a bunch of *exactly* 1000 elements
list, then I'm spending a lot of time in counting elements... for nothing.
One possibility is to have that counter really be dynamic , se when we
return false we divide the counter by two, and when true we it multiply by
1.5 or something with of course reasonable bounds. Looks a little like TCP
:-)
But even like this i'm not very satisfied...

Actually , here's the problem : why do people need fold_right ? ( means :
why don't they use fold_left ? )
Answer : because most of the time they want to build a list in the same
order as the input list.

Ok, so let's provide them a "list only" version of fold_right ( ExtList.fold
? ) that will do the job in a tail-rec way using internals set_cdr to
construct the list in the user-wanted way. This of course does not cover all
the cases, but should be enough to preserve speed where it is needed (btw
enums should be even better for this kind of things ^^;) . The difference of
this fold is that we are iterating from left_to_right but I don't think that
a lot of users actually wants to do so.

Nicolas Cannasse