4

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

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生成结果列表并已经以正确的顺序生成它。我想有必要使用延续来构建列表，但我对函数式编程还很陌生，还没有设法将我的思想包裹在延续上；我能想象的所有替代方法都会将累加器放在结果列表中，或者不允许它由函数返回。

有没有办法做到这一点？

由于这是一个个人学习练习，我更喜欢一个解释如何做的答案，而不是简单地给出完整的代码。

4

2 回答 2

5

没有 a 的方法List.rev是传递一个函数而不是resultList参数。让我们调用那个函数buildResultList。在每一步，该函数将获取列表的已构建尾部，将当前项添加到前面，然后将其传递给上一步的函数，该函数将附加上一个项，将其传递给前一个项的函数-上一步，以此类推。此链中的最后一个函数会将第一项添加到列表中。整个递归循环的结果将是链的最后一个函数（它调用所有以前的函数），然后您将使用空列表作为参数调用它。恐怕这在我不写代码的情况下就已经很清楚了。

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

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

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

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

枚举的方式是调用函数，它会返回下一项加上序列的尾部。然后您可以将您的展开编写为一个函数，该函数返回当前项目 as head，然后仅返回包装在闭包中的自身 as tail。实际上，结果很简单。

于 2016-09-23T13:18:09.987 回答
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
于 2016-09-23T13:50:34.883 回答