递归在SML的入口端是什么样子的

Question

有人可以教我递归对于let-val-in-end的情况是什么样子的吗？我很难理解游行，即循环的崩溃[SML]

示例：'c'表现如何？我是说故障

fun less (nil, x) = nil
    | less (a::b, x) = 
    let
        val c = less(b,x)
    in
        if a < x then a::c else c
    end;

或者x和y在每个循环中的行为如何？我知道它正在解构，就像JS一样。

fun half nil = (nil,nil) 
| half [a] = ([a],nil)
| half (a::b::xs) = 
    let 
        val (x,y) = half(xs)
    in 
        (a::x, b::y)
    end;
    
half [1,2,3]

Answer 1

让我们来看看你的半函数。

fun half nil = (nil, nil) 
  | half [a] = ([a], nil)
  | half (a::b::xs) = 
      let 
        val (x, y) = half(xs)
      in 
        (a::x, b::y)
      end;

当我们计算半[1,2,3]时，这如何减少？

half [1, 2, 3]
(1 :: [3], 2 :: [nil])
([1, 3], [2])

您在＜code＞xs＜code＞上递归调用了＜code＞half＜code＞在本例中为＜code＞[3]。这将返回（[3]，[nil]），因此您将本地绑定x为[3]，而本地绑定y为[nil]。我们将＜code＞a＜/code＞和＜code＞b＜/code＞分别与这些列表进行比较，并得到最终结果。

重要的是要认识到这不是尾递归的，如果样本足够大，就会发生堆栈溢出。

我们可以使用累加器将其转换为尾部递归。通过这样做，所有数据都从一个堆栈帧传递到下一个。不需要任何先前的堆栈帧来完全评估函数。因此，一个好的编译器会将其优化为恒定的堆栈空间。

累加器是一个包含两个列表的元组。

fun split([], (a, b)) = (a, b)
  | split([x], (a, b)) = split([], (x::a, b))
  | split(x::x'::xs, (a, b)) = split(xs, (x::a, x'::b))

现在，如果我们调用拆分（[1,4,7,2,89,12], ([], []))：

split([1, 4, 7, 2, 89, 12], ([], []))
split([7, 2, 89, 12], (1::[], 4::[]))
split([89, 12], (7::1::[], 2::4::[]))
split([89, 12], (7::1::[], 2::4::[]))
split([], (89::7::1::[], 12::2::4::[]))
(89::7::1::[], 12::2::4::[])
([89, 7, 1], [12, 2, 4])

哎呀！他们倒过来了！让我们把蓄能器倒过来。

fun split([], (a, b)) = (List.rev a, List.rev b)
  | split([x], (a, b)) = split([], (x::a, b))
  | split(x::x'::xs, (a, b)) = split(xs, (x::a, x'::b))

但每次调用＜code＞split＜/code＞时都必须指定初始累加器，这很烦人。我们可以创建一个局部函数来隐藏它。

fun split(lst) =
let
  fun split'([], (a, b)) = (List.rev a, List.rev b)
    | split'([x], (a, b)) = split'([], (x::a, b))
    | split'(x::x'::xs, (a, b)) = split'(xs, (x::a, x'::b))
in
  split'(lst, ([], []))
end;

然后< code>split([1，3，7，2，6，8，0，3，7，5])产生< code>([1，7，6，0，7]，[3，2，8，3，5])。

总之:局部绑定本质上与递归没有任何关系。此外，尾部递归更容易推理，并防止堆栈溢出错误。