自定义展开返回累加器

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使用生成的列表并使用正确的顺序生成它.我想有必要使用continuation来构建列表,但我对函数式编程很陌生,并且还没有设法将我的思想包含在继续中; 我能想象的所有替代方案都会将累加器放在结果列表中,或者不允许函数返回它.

有办法做到这一点吗？

由于这是一个个人学习练习,我宁愿回答一个解释如何做,而不是简单地给出完整的代码.

Answer 1

没有a的方法List.rev是传递函数而不是resultList参数.我们称之为该功能buildResultList.在每一步中,此功能将采取名单已建成的尾巴,前面加上目前的项目,然后通过这个从功能前面的步骤,这将追加以前的项目,它从传递给函数previous-上一步,等等.此链中的最后一个函数将在列表中添加第一个项目.整个递归循环的结果将是链的最后一个函数(它调用所有先前的函数),然后您将使用空列表作为参数调用.我担心只要编写代码就可以了.

然而,问题是,对于"更好"的任何定义,这都不会更好.由于计算正在向前进行,并且结果列表是"向后"构建的(head :: tail,Lisp-style),因此必须在某处累积结果.在你的代码中,你将它累积在一个临时列表中,但是如果你修改它以使用continuation,你将把它作为一系列在一个链中相互引用的闭包在堆上累积.有人可能会说,从本质上讲,它只是同一个列表,只是模糊不清.

您可以尝试的另一种方法是使用延迟序列:构建递归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.事实证明,非常简单.