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

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

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?

Brian