I read the sources of the main F # library (v.2.0) and found something quite interesting: it
List.foldBackis implemented through a mutable array, in contrast List.fold, which is pretty simple. Here is the source or you can find here :
let foldArraySubRight (f:OptimizedClosures.FSharpFunc<'T,_,_>) (arr: 'T[]) start fin acc =
let mutable state = acc
for i = fin downto start do
state <- f.Invoke(arr.[i], state)
state
// this version doesn't causes Qaru - it uses a private stack
let foldBack<'T,'State> f (list:'T list) (acc:'State) =
// skipped optimized implementations for known lists
// It is faster to allocate and iterate an array than to create all those
// highly nested stacks. It also means we won't get stack overflows here.
let arr = toArray list
let arrn = arr.Length
foldArraySubRight f arr 0 (arrn - 1) acc
What is the reason not to use the sequel?
Something naive, like the code below, seems to work only 2-3 times slower than the optimized library method. It seems doubtful that it really is "faster allocating and iterating over an array." Also, it is tail recursive, so there is no StackOverflow here.
Did I miss something?
let foldBack2 predicate acc list =
let rec loop list cont =
match list with
| [] -> cont acc
| h::t -> loop t (fun racc -> cont (predicate h racc))
loop list id
source
share