尾递归复制到在F＃列表

我试图通过该序列的第一个元素递归地追加到列表中建立从序列列表：尾递归复制到在F＃列表

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

两个问题：

。得到一个堆栈溢出，这意味着我的尾部recusive工艺很烂

和

。为什么当我把|> Seq.cache放在这里let newS = s |> Seq.skip(1)|> Seq.cache时，代码快了100倍。

（请注意，这只是一个小的锻炼，我知道你能做到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

来源

2010-08-17 jlezard

让newRes = curr :: res - 小改进 – 2010-08-17 14:36:04

改了，谢谢 – jlezard 2010-08-17 14:40:21

你说这只是练习，而是指向我的回答

While or Tail Recursion in F#, what to use when?

，并重申应在可能的情况更青睐应用性/声明结构是有益的。例如。

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

是一个很好的表现方式来表达你的特定功能。

这就是说，如果我没有说“从来没有创建一个大的列表”，我会感到失望。对于庞大的数据，你需要数组或seq。

来源

2010-08-17 14:25:14 Brian

谢谢Brian。不打算在现实生活中使用这个列表:)，只是试图做一个我想要完成的事情的简单例子。（我会改变seq的大小，使事情更合理） – jlezard 2010-08-17 14:33:02

好吧，现在我想你的问题关于StackOverflow是没有意义的。 :) – Brian 2010-08-17 14:39:41

arrg，你骗了我！，我已经将这种改变逆转为一种足够大而可以溢出而又合理的东西:) – jlezard 2010-08-17 14:43:52

在我与F＃短的经验是不要用Seq.skip 1，就像您用尾巴列出一个好主意。 Seq.skip创建一个新的IEnumerable/sequence而不是只跳过n。因此，你的功能会比List.toSeq慢。你应该正确地做到这一点，与

s.GetEnumerator()

并迭代通过序列，并保持一个列表，你对每一个单一的元素。

在这个问题上

Take N elements from sequence with N different indexes in F#

我开始做类似你做什么东西，但发现它是非常缓慢的。请参阅我的方法，了解如何做到这一点。

增加：我写了这个：

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

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

    List.rev res

，结果发现，在方法构建实际执行非常相似（包括反向部分）的东西。但是，它会检查您提供的序列是否实际上是列表或数组。

您将能够使代码完整的功能：（我现在也没有 - could'nt抵抗;-)）

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

来源

2010-08-17 13:59:02

感谢您的评论。仍然想知道堆栈溢出为什么会发生？ – jlezard 2010-08-17 14:10:58

我帮不了你。当谈到F＃时，我是新手。 – 2010-08-17 14:14:09

看到上面更改的代码，谢谢！ – jlezard 2010-08-17 14:22:19

试试下面的代码。

警告：在运行此代码之前，您需要在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-17 14:05:59 JaredPar

你的函数是正确的尾递归，所以递归调用本身不是什么溢出堆栈。相反，问题是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-17 15:13:43 kvb

尾递归复制到在F＃列表

回答

相关问题