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

您在 xs 上递归调用了 half，在本例中为 [3]。这个returns([3], [nil])，所以你本地绑定x是[3]，本地绑定y是[nil]。我们分别对这些列表使用 a 和 b 并得到最终结果。

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

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

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

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

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

SML 中的 let-in-end 递归看起来如何

How does recursion looks like for let-in-end in SML

functional-programming

sml