4

この F# seq 式は末尾再帰のように見えますが、スタック オーバーフロー例外が発生しています (末尾呼び出しが有効になっている場合)。私が欠けているものを誰か知っていますか？

let buildSecondLevelExpressions expressions =
    let initialState = vector expressions |> randomize
    let rec allSeq state = seq {
        for partial in state do
            if count partial = 1
            then yield Seq.head partial
            if count partial > 1 || (count partial = 1 && depth (Seq.head partial) <= MAX_DEPTH) then
                let allUns = partial
                                |> pick false 1
                                |> Seq.collect (fun (el, rr) -> (createExpUnaries el |> Seq.map (fun bn -> add rr bn)))
                let allBins = partial  // Careful: this case alone produces result recursivley only if |numbers| is even (rightly!).
                                |> pick false 2
                                |> Seq.collect (fun (el, rr) -> (createExpBinaries el |> Seq.map (fun bn -> add rr bn)))
                yield! allSeq (interleave allBins allUns)
    }
    allSeq initialState

ご参考までに、重要ではありませんが、pickはシーケンス内の要素の組み合わせを生成するために使用されinterleave、2 つのシーケンスから要素をインターリーブします。vectorのコンストラクタですResizeArray。

4

3 に答える 3

4

Gideon が指摘したように、これは末尾再帰ではありません。これは、「状態」リストに処理する他の要素がまだあるためです。処理する要素のキューが必要なため、この末尾再帰を作成するのは簡単ではありません。

次の疑似コードは、考えられる解決策の 1 つを示しています。work残りの作業を格納するパラメーターを追加しました。呼び出しごとに、最初の要素だけを処理します。他のすべての要素がキューに追加されます。終了したら、キューからさらに作業を取り出します。

let rec allSeq state work = seq { 
    match state with 
    | partial::rest -> 
        // Yield single thing to the result - this is fine
        if count partial = 1 then yield Seq.head partial 
        // Check if we need to make more recursive calls...
        if count partial > 1 || (* ... *) then 
            let allUns, allBins = // ...
            // Tail-recursive call to process the current state. We add 'rest' to 
            // the collected work to be done after the current state is processed
            yield! allSeq (interleave allBins allUns) (rest :: work)
        else
            // No more processing for current state - let's take remaining
            // work from the 'work' list and run it (tail-recursively)
            match work with 
            | state::rest -> yield! allSeq state rest
            | [] -> () //completed
    | _ -> 
        // This is the same thing as in the 'else' clause above. 
        // You could use clever pattern matching to handle both cases at once
        match work with 
        | state::rest -> yield! allSeq state rest
        | [] -> () } //completed
于 2010-07-16T14:45:26.103 に答える
3

シーケンス式内のどの呼び出しが F# の末尾位置にあるかの定義を見つけることができないため、現在の実装のセマンティクスに依存するコードを記述しないことを強くお勧めします。つまり、これは未定義の動作です。

たとえばSeq.length、次のシーケンスを列挙 (たとえば、適用) しようとすると、スタック オーバーフローが発生します。

let rec xs() = seq { yield! xs() }

しかし、Tomas が指摘したように、以下は実際に機能します。

let rec xs n = seq { yield n; yield! xs(n+1) }

私のアドバイスは、常に再帰シーケンス式をSeq.unfold代わりに置き換えることです。この場合、おそらく、実行する作業を蓄積する必要があります (たとえば、左のブランチに再帰するときに、右のブランチをアキュムレータのスタックにプッシュします)。

FWIW、F# 言語リファレンスでさえ、これは間違っています。ツリーを平坦化するための次のコードを提供します。

type Tree<'a> =
   | Tree of 'a * Tree<'a> * Tree<'a>
   | Leaf of 'a

let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Leaf x -> yield x
    }

彼ら自身のコードは、左側の深いツリーをフィードすると、F# インタラクティブをスタック オーバーフローで強制終了します。

于 2010-07-17T19:33:23.100 に答える
1

複数回再帰的に呼び出す可能性があるため、これは末尾再帰にはなりません。擬似コードに変換するには：

allSeq(state)
{
    foreach (partial in state)
    {
        if (...)
        {
            yield ...
        }
        if (...)
        {
            ...
            //this could be reached multiple times
            yield! allSeq(...)
        }
    }
}
于 2010-07-16T13:41:49.893 に答える