2

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

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 ([])

两个问题：

. 得到一个堆栈溢出，这意味着我的尾巴回避策略很糟糕

和

. 为什么当我放在|> Seq.cache这里 时代码要快 100 倍let newS = s |> Seq.skip(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
4

4 回答 4

3

你说这只是一个练习，但指出我的答案很有用

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

并重申，您应该尽可能支持更多的应用性/声明性构造。例如

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

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

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

于 2010-08-17T14:25:14.340 回答
1

Seq.skip 1在我对 F# 的短暂体验中，像使用带有尾部的列表一样使用它并不是一个好主意。Seq.skip创建一个新的IEnumerable/sequence，而不仅仅是跳过 n。因此，您的功能将比List.toSeq. 你应该正确地做到这一点

s.GetEnumerator()

并遍历序列并保存一个列表，其中包含每个元素。

在这个问题

在 F# 中从具有 N 个不同索引的序列中获取 N 个元素

我开始做与您类似的事情，但发现它非常慢。请参阅我的方法以获取有关如何执行此操作的灵感。

补充：我写了这个：

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
于 2010-08-17T13:59:02.057 回答
1

您的函数是正确的尾递归，因此递归调用本身并不是溢出堆栈的内容。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您的初始序列的结果。

于 2010-08-17T15:13:43.353 回答
0

试试下面的代码。

警告：在运行此代码之前，您需要在 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"
于 2010-08-17T14:05:59.240 回答