SML 中 let-in-end 的递归是什么样的

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

让我们看看您的

half

 函数。

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]

时，这是如何减少的？

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

您已在

half

 上递归调用 

xs

，在本例中为 

[3]

。这将返回 

([3], [nil])

，因此本地绑定 

x

 是 

[3]

，本地绑定 

y

 是 

[nil]

。我们分别对这些列表使用 

a

 和 

b

 并得到最终结果。

重要的是要认识到这是

不是尾递归，并且如果样本量足够大，就会发生堆栈溢出。

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

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

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))

现在，如果我们打电话

split([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))

但是每次我们调用

split

 时都必须指定初始累加器，这很烦人。我们可以创建一个本地函数来隐藏它。

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;

然后

split([1, 3, 7, 2, 6, 8, 0, 3, 7, 5])

 产生 

([1, 7, 6, 0, 7], [3, 2, 8, 3, 5])

。

总而言之：本地绑定本质上与递归没有任何关系。此外，尾递归可以更容易推理，并防止堆栈溢出错误。