Как проверить результаты рекурсивного вызова в кодах 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) ~ 1) = ~ 4. Но [MULT, ADD, MULT] не будет действительным, так как (((1 * 1) +2) * ~ 1) = ~ 3.

Я смущен, как проверить, были ли возвращенные результаты k(). Использование = для проверки возвращаемого значения невозможно, так как оно является полиморфным. Есть ли способ справиться с этим?

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