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

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

> Just had an idea for ExtList.fold_right.  Ok, there are basically two
> different possible implementations: the non-tail-recursive version:
[...]

I might have solve the problem with a better implementation :

let max = 1000

let fold_right f l init =
    let rec tail_loop acc = function
       | [] -> acc
       | h :: t -> tail_loop (f h acc) t
    in
    let rec loop n = function
        | [] -> init
        | h :: t ->
            if n < max then
                f h (loop (n+1) t)
            else
                f h (tail_loop init (List.rev t))
    in
    loop 0 l

This way for short list you're only doing some extra count, and for long
list you're ending doing a rev , but only on the remaining part of the list.

Nicolas Cannasse