Why List.foldBack is implemented via mutable Array (and not via continuation)? [closed]

Question

I've been reading F# core library sources (v.2.0) and found something rather interesting:
List.foldBack is implemented via a mutable Array, unlike List.fold which is pretty straightforward. Here's the source or you may find it 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 stack overflow - 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 continuation?
Something naive like the code below seems to work only 2-3 times slower than the highly optimized library method. It seems questionable that it is really "faster to allocate and iterate an array". Also, it is tail recursive, so no StackOverflow here.
Am I missing 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

Answer 1

I can think of a few reasons not to use CPS:

1. you trade memory for stack space (all those continuations live on the heap)
2. CPS is inscrutable to most people
3. as you discovered, it's generally slower than the alternatives (see this question for evidence)

A list can't be easily traversed backward and since arrays can't be beat for sequential access (forward or backward) copying to/from an array is actually pretty efficient. As a challenge, try writing a faster foldBack for 10,000/100,000/100,000,000 elements.

Answer 2

Make the common case fast.

In practice, you often deal with small lists which do not cause stack overflow anyway. As an example, the counterpart of F#'s List.foldBack in OCaml, List.fold_right, isn't tail-recursive or using CPS either.

As users, we don't really care what is the internal implementation. We enjoy the surprise of having both fast and tail-recursive List.foldBack. For instance, this beautiful split function is tail-recursive in F#:

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