需要提示(而不是代码)将此递归函数转换为尾递归？

Question

我有这个函数,它获取字符串和字符串列表的列表,然后返回每个列表中包含传递的字符串但没有传递字符串的所有元素的列表.

myfilter([["a","b"],["c","d"],["e","a","x"]], "a") -> ["b","e","x"]

fun myfilter(list : string list list, s : string) =
case list of
    [] =>  []
   |xs::xs' => case all_except_option(s, xs) of (* helper function that does it for a string and a list of strings *)
                   NONE => []
                  |SOME n => if n = xs
                             then myfilter(xs',s)
                             else n@myfilter(xs',s)

现在这是你可以看到的一个递归函数,我想将它转换为尾递归函数.我熟悉尾递归的例子,但我没有看到如何在上面的函数中做到这一点

Answer 1

当你认为尾递归时,你认为接下来应该是"累加器".

函数不是尾递归的原因是它必须调用自身来获取某些结果,然后对该结果执行某些操作.如果我们可以将该计算移动到递归调用中,那么它的尾递归.

在这种情况下,您正在进行的计算是将两个列表放在一起.所以解决方案是在a中声明的函数let ... in ... end,它接受第三个参数 - 累加器.然后,您可以随时向累加器添加项目.

一个很好的例子是尾递归因子函数.这是正常的阶乘函数:

fun fact 0 = 1
  | fact x = x * fact (x-1)

为了使它具有尾递归性,我们定义了一个带累加器的局部函数,并在那里进行乘法运算.

fun fact x =
let
  fun fact' 0 acc = acc
    | fact' x acc = fact (x-1) (x*acc)
in
  fact' x 1
end

我们使用1作为累加器的起始值,因为乘以1无效.

好的,除此之外,您还可以做一些改进代码的事情.我注意到很多人都这样做:

fun foo xs =
case xs of
    []      => ...
  | (x::xs) => ...

这样做会更好:

fun foo []      = ...
  | foo (x::xs) = ...