list - 自定义展开返回累加器

Question

我正在尝试创建一个自定义展开函数，该函数返回其最后一个累加器值，例如:

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 .在每一步，这个函数都会获取列表的已经构建的尾部，添加当前项，然后将其传递给上一步中的函数，该函数将附加前一项，将其传递给前一项的函数 -上一步，等等。此链中的最后一个函数会将第一个项目添加到列表中。整个递归循环的结果将是链的最后一个函数(它调用所有先前的函数)，然后您将使用空列表作为参数调用该函数。恐怕这已经很清楚了，而无需编写代码。

然而 ，问题是，对于“更好”的任何定义，这不会更好。由于计算是“向前”进行的，结果列表是“向后”构建的(head::tail，Lisp 风格)，您必须在某处累积结果。在您的代码中，您将它累积在一个临时列表中，但是如果您修改它以使用延续，您将在堆上累积它作为一系列在链中相互引用的闭包。有人可能会争辩说，它本质上是同一份 list ，只是被混淆了。

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

最后，由于这是一个学习练习，你也可以自己实现一个惰性序列的等价物。现在，标准的 .NET 序列(又名 IEnumerable<_>，这是 Seq<_> 的别名)本质上是可变的:每次移动到下一项时，您都在更改迭代器的内部状态。你可以这样做，或者，本着学习的精神，你可以做一个不变的等价物。这几乎就像一个列表(即 head::tail)，除了因为它是惰性的，“tail”必须是一个 promise 而不是实际的序列，所以:

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

枚举的方法是调用该函数，它会返回下一项加上序列的尾部。然后，您可以将展开编写为一个函数，该函数将当前项目返回为 head然后将自身包裹在闭包中返回 tail .事实证明，其实很简单。