对于像斐波那契这样的简单问题,编写 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,并且不能硬编码。
我想必须将中间变量更改为序列。
(我喜欢将延续视为一份契约(Contract),上面写着“当你有值(value)时,将其传递给我,然后我将在治疗后将其传递给我的老板”或类似的内容,这会推迟实际执行)
对于棒材切割,我们有
//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 版本的棒切割/对此有什么建议吗?
最佳答案
我假设你想显式地 CPS 一切,这意味着一些像列表理解这样的好东西将会丢失(也许使用异步 block 可以有所帮助,我不太了解 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)] 表达式进行 CPS,则可能还需要一个列表构建函数)。 map 非常有趣,因为它是一个高阶函数,因此需要修改它的第一个参数以采用 CPS 函数。这是 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 中的递归放入延续中。使用map_k、max_k、gen_k(构建从1到某个值的列表),cut-rod 函数可以进行 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))
关于algorithm - 动态规划和连续传递风格,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14046739/