2

フィボナッチのような単純な問題の場合、CPSの記述は比較的簡単です

let  fibonacciCPS n =
  let rec fibonacci_cont a cont =
    if a <= 2 then cont 1
    else
      fibonacci_cont (a - 2) (fun x ->
        fibonacci_cont (a - 1) (fun y ->
          cont(x + y)))

  fibonacci_cont n (fun x -> x)

ただし、ここからのロッドカットの例 （またはアルゴのイントロの本）の場合、クロージャの数は常に2に等しいとは限らず、ハードコーディングすることはできません。

中間変数をシーケンスに変更する必要があると思います。

（継続は、「価値があるときは、それを私に渡して、治療後に上司に渡す」という契約、または実際の実行を延期するものと考えるのが好きです）

ロッドカットについては、

//rod cutting
let p = [|1;5;8;9;10;17;17;20;24;30|]

let rec r n = seq { yield p.[n-1]; for i in 1..(n-1) -> (p.[i-1] + r (n-i)) } |> Seq.max 
[1 .. 10] |> List.map (fun i -> i, r i)

この場合、新しく作成した続きを添付する必要があります

let cont' = fun (results: _ array) -> cont(seq { yield p.[n-1]; for i in 1..(n-1) -> (p.[i-1] + ks.[n-i]) } |> Seq.max)

返されるサブ問題によって作成された「デカルト積」の継続に。ロッドカッティングのCPSバージョンを見た人はいますか/これに関するヒントはありますか？

4

1 に答える 1

2

すべてを明示的にCPSしたいと思います。つまり、リスト内包表記などの優れた機能が失われます（非同期ブロックを使用すると役立つ場合がありますが、F＃はよくわかりません）。したがって、単純な再帰関数から始めます。

let rec cutrod (prices: int[]) = function
    | 0 -> 0
    | n -> [1 .. min n (prices.Length - 1)] |>
           List.map (fun i -> prices.[i] + cutrod prices (n - i)) |>
           List.max

使用するリスト関数のCPSバージョンが必要であることは明らかです（[1 ..（blah）]式もCPSする場合は、map、max、およびおそらくリスト作成関数）。mapは高階関数であるため非常に興味深いので、代わりにCPS-ed関数を使用するように最初のパラメーターを変更する必要があります。CPSList.mapの実装は次のとおりです。

let rec map_k f list k = 
  match list with
    | [] -> k []
    | x :: xs -> f x (fun y -> map_k f xs (fun ys -> k (y :: ys)))

map_kは、他のCPS関数と同様に引数fを呼び出し、map_kの再帰を継続に入れることに注意してください。map_k、max_k、gen_k（1からある値までのリストを作成する）を使用すると、カットロッド関数をCPS処理できます。

let rec cutrod_k (prices: int[]) n k = 
  match n with
    | 0 -> k 0
    | n -> gen_k (min n (prices.Length - 1)) (fun indices ->
               map_k (fun i k -> cutrod_k prices (n - i) (fun ret -> k (prices.[i] + ret))) 
                     indices 
                     (fun totals -> max_k totals k))
于 2012-12-26T23:09:42.553 に答える