From: Brian Hurt <brian.hurt@ql...>  20030613 18:04:23

Just had an idea for ExtList.fold_right. Ok, there are basically two different possible implementations: the nontailrecursive version: let rec fold_right f lst init = match lst with  [] > init  h :: t > f h (fold_right f t init) And the tailrecursive, 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 