f# の morris seq 用に書いたこの「学習コード」がありますが、回避方法がわからないスタック オーバーフローに悩まされています。"morris" は、無限の "see and say" シーケンス (つまり、{{1}、{1,1}、{2,1}、{1,2,1,1}、{1,1,1) を返します。 ,2,2,1}, {3,1,2,2,1,1},...})。
let printList l =
Seq.iter (fun n -> printf "%i" n) l
printfn ""
let rec morris s =
let next str = seq {
let cnt = ref 1 // Stack overflow is below when enumerating
for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do
if cur.[0] <> cur.[1] then
yield!( [!cnt ; cur.[0]] )
cnt := 0
incr cnt
}
seq {
yield s
yield! morris (next s) // tail recursion, no stack overflow
}
// "main"
// Print the nth iteration
let _ = [1] |> morris |> Seq.nth 3125 |> printList
Seq.nth を使用して n 番目の反復を選択できますが、スタック オーバーフローに達する前にしか取得できません。私が持っている再帰の 1 つのビットは末尾再帰であり、本質的にリンクされた一連の列挙子を構築します。問題はそこじゃない。4000番目のシーケンスで「enum」が呼び出されたときです。F# 1.9.6.16 では、以前のバージョンは 14000 を超えていたことに注意してください)。これは、リンクされたシーケンスが解決される方法によるものです。シーケンスは遅延しているため、「再帰」も遅延しています。つまり、seq n は seq n-1 を呼び出し、seq n-2 を呼び出し、以下同様に最初の項目を取得します (最初の # が最悪のケースです)。
が問題を悪化させていることを理解しており[|0|] |> Seq.append str |> Seq.windowed 2、それを排除すれば、生成できる # を 3 倍にすることができます。実際には、コードは十分に機能します。morris の 3125 回目の反復は、長さが 10^359 文字を超えます。
私が実際に解決しようとしている問題は、遅延評価を保持し、選択できる反復のスタック サイズに基づいて制限をなくす方法です。メモリ サイズに基づいて制限を行うための適切な F# イディオムを探しています。
2010年10月更新
F# をもう少しよく学び、Haskell を少し学び、この問題を 1 年以上考え、調査した結果、ようやく自分の質問に答えることができました。しかし、難しい問題はいつもそうですが、問題は間違った質問から始まります。問題はシーケンスのシーケンスではありません。実際には、再帰的に定義されたシーケンスが原因です。私の関数型プログラミングのスキルは少し良くなったので、以下のバージョンで何が起こっているのかを簡単に確認できます。
let next str =
Seq.append str [0]
|> Seq.pairwise
|> Seq.scan (fun (n,_) (c,v) ->
if (c = v) then (n+1,Seq.empty)
else (1,Seq.ofList [n;c]) ) (1,Seq.empty)
|> Seq.collect snd
let morris = Seq.unfold(fun sq -> Some(sq,next sq))
これは基本的に、シーケンスを生成するための Seq 処理関数呼び出しの非常に長いチェーンを作成します。F# に付属している Seq モジュールは、スタックを使用しないとチェーンをたどることができないものです。追加および再帰的に定義されたシーケンスに使用する最適化がありますが、その最適化は、再帰が追加を実装している場合にのみ機能します。
だからこれはうまくいく
let rec ints n = seq { yield n; yield! ints (n+1) }
printf "%A" (ints 0 |> Seq.nth 100000);;
そして、これはスタックオーバーフローを取得します。
let rec ints n = seq { yield n; yield! (ints (n+1)|> Seq.map id) }
printf "%A" (ints 0 |> Seq.nth 100000);;
F# ライブラリが問題であることを証明するために、継続を使用して追加、ペアワイズ、スキャン、および収集を実装する独自の Seq モジュールを作成しました。これで、問題なく 50,000 seq の生成と出力を開始できます (処理が終了したため、終了することはありません)。 10^5697 桁の長さ)。
いくつかの追加メモ:
- 継続は私が探していたイディオムでしたが、この場合は、私のコードではなく、F# ライブラリに入る必要がありました。F# の継続については、Tomas Petricek の Real-World Functional Programmingの本から学びました。
- 私が受け入れた怠惰なリストの回答は、別のイディオムを保持していました。遅延評価。書き直したライブラリでは、遅延型を利用してスタックオーバーフローを回避する必要もありました。
- 怠惰なリストバージョンは運によって機能します（おそらく設計によるものですが、それは私の現在の判断能力を超えています）-構築および反復中に使用されるアクティブパターンマッチングにより、必要な再帰が深くなりすぎる前にリストが値を計算するため、怠惰ですが、スタックオーバーフローを避けるために継続が必要なほど怠惰ではありません。たとえば、2 番目のシーケンスが 1 番目のシーケンスの数字を必要とするときには、すでに計算されています。つまり、LL バージョンは厳密にはシーケンス生成の JIT 遅延ではなく、リスト管理のみです。