1

好的，所以我正在尝试将此函数更改为尾递归。我对尾递归的定义是使用“本地辅助函数”来累积我的答案并返回它而不递归调用主函数。

这些功能正常工作。

fun same_string(s1 : string, s2 : string) =
s1 = s2

fun all_except_option (name, []) = NONE
  | all_except_option (name, x::xs)=
case same_string (x , name) of
true  => SOME xs
  | false => case all_except_option(name,xs) of
         NONE   => NONE
           | SOME z => SOME(x::z)

fun get_substitutions1 ([],name2)    = [] (*get_substitutions2 is same but tail recursive *)
  | get_substitutions1 (x::xs,name2) = 
    case all_except_option (name2,x) of
        NONE   => get_substitutions1 (xs,name2)
      | SOME z  => z @ get_substitutions1(xs,name2)

所以这是我对尾递归的尝试，但它不起作用，我认为我缺少一些相当基本的东西，由于我缺乏 SML 经验，我忽略了这些东西。

fun get_substitutions2 (lst,name3) = 
let fun aux (xs,acc) =
 case all_except_option(name3,x::xs) of
     NONE   => aux(xs, acc)
   | SOME z => aux(xs, z::acc)
in
aux(lst,[])
end

和

fun get_substitutions2 (lst,name3) = 
let fun aux (xs,acc) =
 case all_except_option(name3,x::xs) of
     NONE   => aux(xs, acc)
   | SOME z => aux(xs, z@acc)
in
aux(lst,[""])
end

两个“get_substitutions”函数都应该做同样的事情。将 String1 与字符串列表列表进行比较，返回由包含 String1 减去 String1 的所有列表组成的单个列表。

我尝试使用尾递归导致了以下错误。

Error: unbound variable or constructor: x

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
             ../compiler/TopLevel/interact/evalloop.sml:44.55
             ../compiler/TopLevel/interact/evalloop.sml:296.17-

以下是一些调用示例get_substitutions2：

get_substitutions2 ([["foo"],["there"]], "foo"); (* = [] *)
get_substitutions2 ([["fred","fredrick","freddie","F","freddy"],["Will","William","Willy","Bill"]],"Bill"); (* = ["Will","William","Willy"] *)
get_substitutions2 ([["a","b"],["a","c"],["x","y"]], "a"); (* = ["c","b"] *)
4

1 回答 1

2

您需要get_substitutions1在aux函数定义中使用相同的模式：

fun get_substitutions2 (lst,name3) = 
let fun aux ([],acc) = acc (* BASE CASE *)
      | aux (x::xs,acc) =  (* BINDING x IN PATTERN *)
 case all_except_option(name3,x) of
     NONE   => aux(xs, acc)
   | SOME z => aux(xs, z@acc)
in
aux(lst,[])
end
于 2013-10-21T04:24:04.837 回答