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

[John M. S. <sk...@oz...>]

Brian Hurt wrote:

> Just had an idea for ExtList.fold_right.  Ok, there are basically two 
> different possible implementations: the non-tail-recursive version:
> 
> let rec fold_right f lst init =
>     match lst with
>         | [] -> init
>         | h :: t -> f h (fold_right f t init)
> 
> And the tail-recursive, list reversing version:
> 
> let fold_right f lst init =
>     let rec loop l accu =
>         match l with 
>             [] -> accu
>             | h :: t -> loop t (f h accu)
>     in
>     loop (List.rev lst) init
>     
> 
> The first one is faster for short lists, but stack overflows on long 
> lists.  The second one never overflows, but is slower for short lists.
> 
> 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:
> 
> let fold_right f lst init =
>     let max = 1000 in
>     let rec toolong len = function
>         | [] -> false
>         | h :: t -> if len >= max then true else toolong (len + 1) t
>     and revloop accu = function
>         | [] -> accu
>         | h :: t -> revloop (f h accu) t
>     and ntrloop = function
>         | [] -> init
>         | h :: t -> f h (ntrloop t)
>     in
>     if toolong 0 lst then
>         revloop init (List.rev lst)
>     else
>         ntrloop lst
> 
> Thoughts?  Comments?  Benchmarks?

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

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

	fold_right
	rev_fold_right

The fact is, I'll often chose rev_fold_right
because I WANT the list reversed.

I suspect the way to handle a dynamic trade off is:

	fold_right_dynamic estimate f lst init

where 'estimate' is provided by the client.
you don't count the list and decide, you decide based
on the client's estimate. The client can then:

	a) count the list, or otherwise create
	an estimate

	b) curry the function on the estimate

Example: in my Felix compiler I have lists of function
parameters. Well, I know they're short, i don't have to
count them, and if someone writs a function with
2000 parameters, well, I just don't care if there's
a minor slow down :-)

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850