时间戳

首页 > 解决方案 > 使用延续的列表的产品

ocaml - 使用延续的列表的产品

问题描述

我的目标是编写一个 times 类型的函数int list -> int，它接受一个ints 列表，并使用 continuations返回一个int这样的结果，即 that = 中所有s 的int乘积。例如返回。intint listtimes [2;2;3]12

这是我到目前为止所拥有的：

let times l = 
 let rec times' l c = match l with
 | [] -> c []
 | h::h2::t -> times' (h*h2::t) (fun r -> c ( r))
 | h :: [] -> times' [] (fun r -> c (h::[]))
 in
  times' l (fun r -> r) ;;

我的代码有问题

  1. 它返回一个 int 列表，其中一个元素是结果（输入中所有ints 的乘法int list）

  2. 我觉得这并没有真正使用延续，这似乎是一个正常的尾递归函数，但我不确定，因为我仍然不太熟悉这种编程风格。

标签： ocamlmultiplicationcontinuationscontinuation-passing

解决方案

您以递归调用的方式在参数中进行了计算，但您应该继续进行。对于 CPS，您应该做的是“增长”给定的延续。

let times l =
  let rec aux l c =
    match l with
    | [] -> c 1  (* I assume that (times []) is one, and pass it to the next computation c. *)
    | n::ns -> aux ns (fun x -> c (n * x))  (* In a new continuation: For a given value x, multiply by n, and pass it to the next computation c. *)
  in aux l (fun r -> r)

此外，解释 CPS 和直接风格之间差异的示例，用Wikipedia中的“Continuation-passing style”编写，可能会有所帮助。

推荐阅读