10

次の継続モナドを使用します。

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

以下でスタックオーバーフローが発生する理由がわかりません。

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! xs = map xs
                return f x :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

以下はそうではありませんが：

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! v = fun g -> g(f x)
                let! xs = map xs
                return v :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)
4

2 に答える 2

7

例を修正するには、このメソッドをモナドの定義に追加します。

member this.Delay(mk) = fun c -> mk () c

どうやらオーバーフローする部分は、 の再帰呼び出しでの大きな入力リストの破壊ですmap。それを遅らせることで問題は解決します。

2 番目のバージョンでは、への再帰呼び出しを別の への脱糖と追加のラムダのmap後ろに置き、実際にはへの再帰呼び出しを遅らせることに注意してください。let!Bindmap

この結論に達する前に、いくつかの誤った道をたどらなければなりませんでした。助けになったのは、再帰呼び出しが遅れない限り、それStackOverflowがスローされることを観察することでしOCamlた (より高い ではありますが)。NTCOにはいくつF#かの癖がOCamlありますが、より証明されているため、問題は実際にはコンパイラではなくコードにあると確信しました。

let cReturn x = fun k -> k x
let cBind m f = fun c -> m (fun a -> f a c)

let map f xs =
  (* inner map loop overflows trying to pattern-match long lists *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (map xs) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fixed f xs =
  (* works without overflowing by delaying the recursive call *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fused f xs =
  (* manually fused version avoids the problem by tail-calling `map` *)
  let rec map xs k =
    match xs with
      | [] -> k []
      | x :: xs ->
        map xs (fun xs -> k (f x :: xs)) in
  map xs (fun x -> x)
于 2012-06-25T14:47:57.063 に答える
4

F＃コンパイラは、あまり賢くない場合があります。最初のケースでは、F＃コンパイラはmap xs次に計算f xしてから結合するためmap xs、テール位置にはありません。map xs2番目のケースでは、テール位置になるように簡単に並べ替えることができます。

于 2012-06-25T12:18:33.520 に答える