0

所以我正在开发一个函数来从 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，可接受的操作列表应该是 [ADD,ADD,MULT] 或 [ADD,MULT,MULT]，因为 ((((1+1)+2 )*~1) = ((1+1) 2 ~1) = ~4。但是 [MULT,ADD,MULT] 将无效，因为 (((1*1)+2)*~​​1) = ~3。

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

4

1 回答 1

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
于 2015-02-23T17:12:34.260 回答