自定义展开返回累加器

Question

我正在尝试创建一个自定义展开函数，returns 它的最后一个累加器值如下：

val unfold' : generator:('State -> ('T * 'State) option) -> state:'State -> 'T list * 'State

我设法做到了以下几点：

let unfold' generator state =
    let rec loop resultList state =
        match generator state with
        | Some (value, state) -> loop (value :: resultList) state
        | None -> (List.rev resultList), state
    loop [] state

但我想避免 List.rev 结果列表并以正确的顺序生成它。我想有必要使用延续来构建列表，但我对函数式编程还很陌生，还没有设法将我的思想集中在延续上；我能想到的所有替代方案都会将累加器放在结果列表中，或者不允许它由函数返回。

有什么办法吗？

由于这是个人学习练习，我更希望得到解释如何操作的答案，而不是简单地给出完整的代码。

Answer 1

没有 List.rev 的方法是传递一个函数而不是 resultList 参数。我们称该函数为 buildResultList。在每个步骤中，此函数将获取列表的已构建尾部，添加当前项，然后将其传递给 previous 步骤中的函数，后者将附加 previous 项，将其传递给 previous-previous 步骤中的函数，依此类推。该链中的最后一个函数会将第一个项目添加到列表中。整个递归循环的结果将是链的 last 函数（它调用所有之前的函数），然后您可以用空列表作为参数调用它。恐怕这已经很清楚了，而无需编写代码。

然而，问题是，对于 "better" 的任何定义，这都不会更好。由于计算正在进行 "forward"，并且结果列表已构建 "backward"（head :: tail，Lisp 风格），您必须来累积结果某处。在你的代码中，你将它累积在一个临时列表中，但如果你修改它以使用延续，你将把它累积在堆上作为一系列在链中相互引用的闭包。有人可能会争辩说，它本质上是同一个列表，只是被混淆了。

您可以尝试的另一种方法是改用惰性序列：构建递归 seq 计算，它将 yield 当前项目然后 yield! 本身。然后您可以枚举这个序列，它不需要 "temporary" 存储。但是，如果你最后还想得到一个列表，你就必须通过List.ofSeq将序列转换为列表，猜猜这将如何实现？理论上，从纯数学的角度来看，List.ofSeq 将以完全相同的方式实现：首先构建一个临时列表，然后将其反转。但是 F# 库在这里作弊：它以可变方式构建列表，因此不必反转。

最后，由于这是一个学习练习，您还可以自己实现一个惰性序列的等价物。现在，标准的 .NET 序列（又名 IEnumerable<_>，这是 Seq<_> 的别名）本质上是 mutable：你正在改变的内部状态每次移动到下一个项目时迭代器。你可以这样做，或者，本着学习的精神，你可以做一个不变的等价物。那将是几乎就像一个列表（即 head::tail），除了因为它是 lazy，所以 "tail" 有成为一个承诺而不是实际的顺序，所以：

type LazySeq<'t> = LazySeq of (unit -> LazySeqStep<'t>)
and LazySeqStep<'t> = Empty | Cons of head: 't * tail: LazySeq<'t>

枚举的方式是调用函数，它会return给你下一项加上序列的尾部。然后，您可以将展开写成一个函数，将 return 的当前项作为 head，然后将 return 本身包裹在闭包中作为 tail。其实很简单。

Answer 2

感谢 Fyodor Soikin 的回答，这是结果函数：

let unfold' generator state =
    let rec loop build state =
        match generator state with
        | Some (value, state) -> loop (fun newValue -> build (value :: newValue)) state
        | None -> (build []), state
    loop id state

自定义展开返回累加器

custom unfold returning the accumulator

recursion

f#

tail-recursion

list

unfold