将 seq 尾部递归复制到 F# 中的列表

Question

我试图通过将序列的第一个元素递归地附加到列表来从序列构建列表：

open System


let s = seq[for i in 2..4350 -> i,2*i]

let rec copy s res = 
     if  (s|>Seq.isEmpty)  then 
         res
     else
         let (a,b) = s |> Seq.head
         Console.WriteLine(string a)
         let newS = s |> Seq.skip(1)|> Seq.cache
         let newRes = List.append res ([(a,b)])
         copy newS newRes



copy s ([])

两个问题：

。出现堆栈溢出，这意味着我的尾部递归策略很

。

糟糕 为什么当我输入 |> 时，代码速度快了 100 倍？ Seq.cache 此处 let newS = s |>序列跳过(1)|> Seq.cache。

（注意这只是一个小练习，我知道你可以做 Seq.toList 等。）

非常感谢

一种有效的方法是（这两点对我来说仍然有点奇怪）：

let toList (s:seq<_>) =

    let rec copyRev res (enum:Collections.Generic.IEnumerator<_*_>) = 
         let somethingLeft = enum.MoveNext()
         if  not(somethingLeft)  then 
             res
         else
             let curr = enum.Current
             Console.WriteLine(string curr)
             let newRes = curr::res
             copyRev newRes enum

    let enumerator = s.GetEnumerator()
    (copyRev ([]) (enumerator)) |>List.rev

Answer 1

你说这只是一个练习，但指出我对

F# 中的 while 或尾递归，何时使用什么？

并重申您应该尽可能支持更多应用性/声明性结构。 Eg

let rec copy2 s = [
    for tuple in s do
        System.Console.WriteLine(string(fst tuple))
        yield tuple
    ]

是表达特定功能的一种很好且高效的方式。

也就是说，如果我不说“永远不要创建那么大的列表”，我会感到失职。对于海量数据，您需要数组或序列。

Answer 2

根据我使用 F# 的短暂经验，像使用尾部列表一样使用 Seq.skip 1 并不是一个好主意。 Seq.skip 创建一个新的 IEnumerable/sequence 而不仅仅是跳过 n。因此，您的函数将比 List.toSeq 慢很多。您应该正确地执行命令

s.GetEnumerator()

并迭代序列并保存一个包含每个元素的列表。

在这个问题中

从序列中取出 N 个元素 N F# 中的不同索引

我开始做与您类似的事情，但发现它非常慢。请参阅我的方法以获取如何做到这一点的灵感。

补充：我写了这个：

let seqToList (xs : seq<'a>) =
    let e = xs.GetEnumerator()
    let mutable res = []

    while e.MoveNext() do
        res <- e.Current :: res

    List.rev res

并发现内置方法实际上做了一些非常相似的事情（包括相反的部分）。但是，它会检查您提供的序列实际上是列表还是数组。

您将能够使代码完全发挥作用：（我现在也这样做了 - 无法抗拒；-））

let seqToList (xs : seq<'a>) =
        Seq.fold (fun state t -> t :: state) [] xs |> List.rev

Answer 3

您的函数是正确的尾递归，因此递归调用本身并不是堆栈溢出的原因。相反，问题在于 Seq.skip 在递归使用时表现不佳，正如其他人指出的那样。例如，这段代码在我的机器上溢出了堆栈：

let mutable s = seq { 1 .. 20001 }
for i in 1 .. 20000 do
  s <- Seq.skip 1 s
let v = Seq.head s

也许您可以看到与您自己的代码的模糊连接，该代码最终也占据了由于重复应用 Seq.skip 1 所产生的序列的头部你的初始序列。

Answer 4

尝试以下代码。

警告：在运行此代码之前，您需要在 Visual Studio 中启用尾调用生成。这可以通过项目属性页面上的“构建”选项卡来完成。如果未启用此功能，代码将在 StackOverflow 中处理延续。

open System
open System.Collections.Generic

    let s = seq[for i in 2..1000000 -> i,2*i]

    let rec copy (s : (int * int) seq) = 
        use e = s.GetEnumerator()
        let rec inner cont =
            if e.MoveNext() then 
                let (a,b) = e.Current
                printfn "%d" b
                inner (fun l -> cont (b :: l))
            else cont []
        inner (fun x -> x)

    let res = copy s 
    printfn "Done"