如何查看CPS代码中的递归调用结果

Question

所以我正在研究一个函数，从 int 列表中找到对目标数字的一些有效算术运算。不允许使用 throw/callac。此处只有 add 和 mul 是有效的算术运算，并且它们是关联的。

datatype operation = ADD | MULT

(* find_op: int -> int list -> (operatino list -> 'a) -> (unit -> 'a) -> 'a *)
fun find_op x [] s k = k()
  | find_op x [y] s k = if x=y then s([]) else k()
  | find_op x (y1::y2::ys) s k =
    let
      val add = find_op x ((y1+y2)::ys) (fn a => s(ADD::a)) k
      val mul = find_op x ((y1*y2)::ys) (fn a => s(MULT::a)) k
    in
      need some work here
    end

函数应该像下面这样工作：

给定列表 [1,1,2,~1] 和目标编号 ~4, accpeted 操作列表应该是 [ADD,ADD,MULT] 或 [ADD,MULT,MULT], 因为 (((1 +1)+2)*~1) = ((1+1)2~1) = ~4。但是 [MULT,ADD,MULT] 将无效，因为 (((1*1)+2)*~1) = ~3.

我很困惑如何检查 returned 结果是否为 k()。使用 = 来检查 return 值是不可能的，因为它是多态的。有什么方法可以处理吗？

Answer 1

你要做的是使用这两种策略，首先尝试通过ADD减少数字，然后通过MULT减少数字，但是依次.为此，您需要为第一个选择的策略的结果提供自定义失败延续 (k)。如果该策略失败，则尝试继续失败中的第二个策略。

您不能同时尝试两种策略并让它们都成功。该函数类型不允许返回多个正确答案。为此，您需要成功延续的类型为 operation list list.

datatype operation = ADD | MULT

fun opToString ADD  = "ADD"
  | opToString MULT = "MULT"

(* find_op: int -> int list -> (operation list -> 'a) -> (unit -> 'a) -> 'a *)
fun find_op x [] s k               = k ()
  | find_op x [y] s k              = if x = y then s [] else k ()
  | find_op x (y1 :: y2 :: ys) s k =
    let
      (* You need a custom failure continuation that tries the MULT variant
       * if the ADD one fails.
       *)
      fun whenAddFails () =
        find_op x ((y1 * y2) :: ys) (fn a => s (MULT :: a)) k
      val add =
        find_op x ((y1 + y2) :: ys) (fn a => s (ADD :: a)) whenAddFails
    in
      add
    end


fun test () =
  let
    val opList = [1,1,2,~1]
    val target = ~4
    fun success ops =
      "success: " ^ (String.concatWith " " (List.map opToString ops))
    fun failure () =
      "couldn't parse numbers as an operation list"
  in
    find_op target opList success failure
  end

如何查看CPS代码中的递归调用结果

How to check recursive call results in CPS codes

sml

continuation