6

我一直在阅读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
4

2 回答 2

10

我可以想到几个不使用 CPS 的理由：

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

无法轻松地向后遍历列表，并且由于无法击败数组以进行顺序访问（向前或向后）复制到数组或从数组复制实际上非常有效。foldBack作为一项挑战，尝试为 10,000/100,000/100,000,000 个元素编写更快的代码。

于 2012-10-01T20:25:51.453 回答
5

快速制作普通案例。

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

作为用户，我们并不真正关心内部实现是什么。我们享受同时拥有 fast 和 tail-recursive 的惊喜List.foldBack。例如，这个漂亮的拆分函数在 F# 中是尾递归的：

let split list = List.foldBack (fun x (l,r) -> x::r, l) list ([],[])
于 2012-10-01T20:27:25.297 回答