尾遞歸複製到在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＃列表

回答

相關問題