动态编程和延续通过样式

Question

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

然而，对于从这里（或算法的书籍介绍）的杆切割的情况，闭合数并不总是等于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版本的杆切割/有任何提示吗？

Answer 1

我假设您想明确CPS所有内容，这意味着一些不错的东西将丢失列表理解（也许使用async块可以帮助您，我不太了解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版本（如果您想cps [1 ..（blah）]表达式，则映射，最大以及列表构建功能）。MAP非常有趣，因为它是一个高阶函数，因此需要修改其第一个参数才能采用CPS-ED功能。这是CPS列表的实现。映射：

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