Why is List.foldBack implemented through a mutable array (and not through a continuation)?

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
+5
source share
2

CPS:

  • ( )
  • CPS
  • , , (. ).

, ( ), / . foldBack 10 000/100 000/100 000 000 .

+10

.

, . , F # List.foldBack OCaml, List.fold_right, CPS.

, . , List.foldBack. , split F #:

let split list = List.foldBack (fun x (l,r) -> x::r, l) list ([],[])
+5

All Articles