9

開示：これは、私が維持しているF＃ランダムテストフレームワークであるFsCheckで発生しました。私には解決策がありますが、私はそれが好きではありません。さらに、私は問題を理解していません-それは単に回避されただけです。

（大きな単語を使用する場合はモナディック）シーケンスのかなり標準的な実装は次のとおりです。

let sequence l = 
    let k m m' = gen { let! x = m
                       let! xs = m'
                       return (x::xs) }
    List.foldBack k l (gen { return [] })

genは、選択した計算ビルダーで置き換えることができます。残念ながら、その実装はスタックスペースを消費するため、リストが十分に長い場合、最終的にスタックがオーバーフローします。問題は、なぜですか。原則として、foldBackは末尾再帰ではないことは知っていますが、F＃チームの巧妙なバニーは、foldBackの実装でそれを回避しました。計算ビルダーの実装に問題はありますか？

実装を以下に変更すると、すべて問題ありません。

let sequence l =
    let rec go gs acc size r0 = 
        match gs with
        | [] -> List.rev acc
        | (Gen g)::gs' ->
            let r1,r2 = split r0
            let y = g size r1
            go gs' (y::acc) size r2
    Gen(fun n r -> go l [] n r)

完全を期すために、Genタイプと計算ビルダーはFsCheckソースにあります。

4

2 に答える 2

9

Tomasの答えに基づいて、2つのモジュールを定義しましょう。

module Kurt = 
    type Gen<'a> = Gen of (int -> 'a)

    let unit x = Gen (fun _ -> x)

    let bind k (Gen m) =     
        Gen (fun n ->       
            let (Gen m') = k (m n)       
            m' n)

    type GenBuilder() =
        member x.Return(v) = unit v
        member x.Bind(v,f) = bind f v

    let gen = GenBuilder()


module Tomas =
    type Gen<'a> = Gen of (int -> ('a -> unit) -> unit)

    let unit x = Gen (fun _ f -> f x)

    let bind k (Gen m) =     
        Gen (fun n f ->       
            m n (fun r ->         
                let (Gen m') = k r        
                m' n f))

    type GenBuilder() =
        member x.Return v = unit v
        member x.Bind(v,f) = bind f v

    let gen = GenBuilder()

少し単純化するために、元のシーケンス関数を次のように書き直してみましょう。

let rec sequence = function
| [] -> gen { return [] }
| m::ms -> gen {
    let! x = m
    let! xs = sequence ms
    return x::xs }

これで、またはで定義されているsequence [for i in 1 .. 100000 -> unit i]かどうかに関係なく、最後まで実行されます。問題は、定義を使用するときにスタックオーバーフローを引き起こすことではなく、呼び出しから返された関数が呼び出されたときにスタックオーバーフローを引き起こすことです。sequenceKurt.genTomas.gensequencesequence

これがなぜそうなのかを理解するためsequenceに、基礎となるモナディック操作の観点からの定義を拡張してみましょう。

let rec sequence = function
| [] -> unit []
| m::ms ->
    bind (fun x -> bind (fun xs -> unit (x::xs)) (sequence ms)) m

Kurt.unitと値をインライン化しKurt.bind、狂ったように単純化すると、

let rec sequence = function
| [] -> Kurt.Gen(fun _ -> [])
| (Kurt.Gen m)::ms ->
    Kurt.Gen(fun n ->
            let (Kurt.Gen ms') = sequence ms
            (m n)::(ms' n))

let (Kurt.Gen f) = sequence [for i in 1 .. 1000000 -> unit i] in f 0これで、呼び出しがスタックをオーバーフローする理由が明らかfになりました。結果の関数のシーケンスと評価に末尾再帰以外の呼び出しが必要になるため、再帰呼び出しごとに1つのスタックフレームがあります。

代わりに、の定義にインラインTomas.unit化して、次の簡略化されたバージョンを取得します。Tomas.bindsequence

let rec sequence = function
| [] -> Tomas.Gen (fun _ f -> f [])
| (Tomas.Gen m)::ms ->
    Tomas.Gen(fun n f ->  
        m n (fun r ->
            let (Tomas.Gen ms') = sequence ms
            ms' n (fun rs ->  f (r::rs))))

このバリアントについての推論には注意が必要です。（Tomasが彼の回答で示しているように）任意に大きな入力に対してスタックを爆破しないことを経験的に検証でき、この事実を確信するために評価を段階的に進めることができます。ただし、スタックの消費量は、Gen渡されたリスト内のインスタンスによって異なり、それ自体が末尾再帰ではない入力に対してスタックをブローする可能性があります。

// ok
let (Tomas.Gen f) = sequence [for i in 1 .. 1000000 -> unit i]
f 0 (fun list -> printfn "%i" list.Length)

// not ok...
let (Tomas.Gen f) = sequence [for i in 1 .. 1000000 -> Gen(fun _ f -> f i; printfn "%i" i)]
f 0 (fun list -> printfn "%i" list.Length)
于 2011-07-07T18:02:07.260 に答える
5

正解です。スタックオーバーフローが発生する理由bindは、モナドの操作が末尾再帰である必要があるためです（フォールディング中に値を集約するために使用されるため）。

FsCheckで使用されるモナドは、基本的に状態モナドです（現在のジェネレーターといくつかの数値を保持します）。私はそれを少し単純化して、次のようなものを得ました：

type Gen<'a> = Gen of (int -> 'a)

let unit x = Gen (fun n -> x)

let bind k (Gen m) = 
    Gen (fun n -> 
      let (Gen m') = k (m n) 
      m' n)

ここで、bind関数は呼び出しkてからさらに作業を行うため、末尾再帰ではありません。モナドを継続モナドに変更できます。これは、状態と継続を受け取る関数として実装されます。これは、結果を引数として呼び出される関数です。このモナドでは、bind末尾再帰を作成できます。

type Gen<'a> = Gen of (int -> ('a -> unit) -> unit)

let unit x = Gen (fun n f -> f x)

let bind k (Gen m) = 
    Gen (fun n f -> 
      m n (fun r -> 
        let (Gen m') = k r
        m' n f))

次の例では、スタックオーバーフローは発生しません（元の実装で発生しました）。

let sequence l = 
  let k m m' = 
    m |> bind (fun x ->
      m' |> bind (fun xs -> 
        unit (x::xs)))
  List.foldBack k l (unit [])

let (Gen f) = sequence [ for i in 1 .. 100000 -> unit i ]
f 0 (fun list -> printfn "%d" list.Length)
于 2011-05-30T21:04:01.347 に答える