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

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




我一直在阅读F# core library sources (v.2.0) 并发现了一些有趣的东西:List.foldBack是通过可变数组实现的，不像 List.fold这很简单。这是来源，或者您可以找到它 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

不使用延续的原因是什么？
像下面的代码一样天真的东西似乎只比高度优化的库方法慢 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 的原因:

你用内存交换堆栈空间(所有这些延续都在堆上)

CPS对大多数人来说是高深莫测的

正如您所发现的，它通常比替代方案慢(有关证据，请参阅 this question)

一个列表不能轻易地向后遍历，并且因为数组不能被顺序访问(向前或向后)复制到/从一个数组复制实际上是非常有效的。作为挑战，尝试写一个更快的 foldBack对于 10,000/100,000/100,000,000 个元素。