SML中let-val-in-end结构的递归执行逻辑及实例答疑

SML let-val-in-end 递归执行逻辑核心 #

SML的执行顺序是严格的从上到下、先绑定后使用，碰到let val 变量 = 递归调用 in 逻辑 end结构时，一定会先完整执行完递归调用拿到返回值绑定给变量，再执行in后的代码，整体是「先逐层深入递归到终止条件，再逐层向上返回计算结果」的逻辑。

1. less函数的变量c行为及执行拆解 #

这个less函数的作用是筛选输入列表中所有小于参数x的元素，返回由这些元素组成的新列表。

c的本质 #

c存储的是当前列表去掉第一个元素后，剩余部分调用less得到的筛选结果。当前层只需要判断第一个元素是否小于x，是就把该元素拼到c前面返回，否则直接返回c即可。

完整执行拆解示例（以less([3,1,4,2], 3)为例） #

第1层调用：less([3,1,4,2], 3)
匹配分支：a::b → a=3，b=[1,4,2]
第一步执行val c = less([1,4,2], 3) → 进入第2层调用

第2层调用：less([1,4,2], 3)
匹配分支：a::b → a=1，b=[4,2]
第一步执行val c = less([4,2], 3) → 进入第3层调用

第3层调用：less([4,2], 3)
匹配分支：a::b → a=4，b=[2]
第一步执行val c = less([2], 3) → 进入第4层调用

第4层调用：less([2], 3)
匹配分支：a::b → a=2，b=nil
第一步执行val c = less(nil, 3) → 进入第5层调用

第5层调用：less(nil, 3)
匹配分支：nil → 直接返回nil

// 开始逐层向上返回
第4层拿到c=nil，判断a=2<3成立，返回2::nil → [2]，作为第3层的c
第3层拿到c=[2]，判断a=4<3不成立，直接返回c → [2]，作为第2层的c
第2层拿到c=[2]，判断a=1<3成立，返回1::[2] → [1,2]，作为第1层的c
第1层拿到c=[1,2]，判断a=3<3不成立，直接返回c → [1,2]

最终执行结果：[1,2]

2. half函数的x、y行为及执行拆解 #

这个half函数的作用是把输入列表拆分为两个子列表：原列表奇数位置的元素归入第一个子列表，偶数位置的元素归入第二个子列表。

x、y的本质 #

每次递归调用half(xs)返回的是「去掉当前层前两个元素后，剩余列表xs拆分完成的两个子列表」：

• x是剩余列表的奇数位置元素组成的子列表
• y是剩余列表的偶数位置元素组成的子列表
  当前层的第一个元素a对应原列表的奇数位，拼到x前面返回；第二个元素b对应原列表的偶数位，拼到y前面返回即可。

完整执行拆解（以half [1,2,3]为例） #

第1层调用：half [1,2,3]
匹配分支：a::b::xs → a=1，b=2，xs=[3]
第一步执行val (x,y) = half([3]) → 进入第2层调用

第2层调用：half [3]
匹配分支：[a] → 直接返回([3], nil)

// 开始逐层向上返回
第1层拿到x=[3]，y=nil，执行in内逻辑返回(a::x, b::y) → (1::[3], 2::nil) → ([1,3], [2])

最终执行结果：([1,3], [2])

内容的提问来源于stack exchange，提问作者asworeya shrestha