algorithm - 动态编程和延续传递风格

对于像fibonacci这样的简单问题，编写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)

但是，对于here中的杆切割示例（或书本intro to algo），闭合数不总是等于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)

在这种情况下，我需要附加新创建的continuation

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版的棒切割/有什么建议？

最佳答案

我假设您想要显式地对所有内容进行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版本（map、max，如果您还想对[1..（blah）]expression进行CPS处理，那么可能还需要一个列表生成函数）map是一个很有趣的函数，因为它是一个高阶函数，所以需要修改它的第一个参数，使之成为一个CPS-ed函数以下是cps list.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中的递归放入continuation中使用map_k、max_k、gen_k（从1到某个值建立一个列表），切割杆函数可以是cps ed：

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))