为什么List.foldBack是通过可变数组实现的(而不是通过延续)？

Question

我一直在阅读F#核心库源代码(v.2.0)并发现了一些相当有趣的东西:
List.foldBack通过一个可变数组实现,不像那样List.fold非常简单.这是源代码,或者您可以在此处找到它:

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

不使用延续的原因是什么？
像下面的代码一样天真似乎只比高度优化的库方法慢2-3倍.看起来真的"分配和迭代数组更快"似乎值得怀疑.此外,它是尾递归,因此这里没有StackOverflow.
我错过了什么吗？

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

我可以想到一些不使用CPS的原因:

1. 你交换内存的堆栈空间(所有这些延续存在于堆上)
2. CPS对大多数人来说都是不可理解的
3. 正如你所发现的那样,它通常比替代品慢(请参阅此问题以获取证据)

列表不能轻易地向后遍历,并且由于数组不能被顺序访问(向前或向后),因此向/从数组复制实际上非常有效.作为挑战,尝试更快地foldBack为10,000/100,000/100,000,000元素编写代码.

Answer 2

快速通用案例.

在实践中,您经常处理不会导致堆栈溢出的小列表.例如,List.foldBackOCaml中的F#对应List.fold_right不是尾递归或使用CPS.

作为用户,我们并不关心内部实现是什么.我们喜欢快速和尾递归List.foldBack.例如,这个漂亮的分割函数在F#中是尾递归的:

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