SML递归函数number_in_month遍历列表的执行逻辑疑问

嘿，作为SML新手，这种递归写法一开始摸不着头脑太正常啦！其实这不是什么特殊的内置机制，而是SML核心特性之一的模式匹配在起作用，它帮你简化了列表遍历的代码，咱们一步步拆解来看：

先看函数的模式匹配结构 #

你贴的函数定义是：

fun number_in_month ([], _) = 0 
  | number_in_month ((_,x2,_) :: xs, m) = 
      if x2 = m then 1 + number_in_month(xs, m) else number_in_month(xs, m)

这里的关键是第二个分支的((_,x2,_) :: xs, m)：

• ::是SML里的列表构造运算符，用来把一个头部元素和一个尾部列表拼接起来。反过来，用它做模式匹配的时候，就可以直接解构列表：把列表的第一个元素（这里是一个三元组(_,x2,_)，提取出第二个值x2）和剩下的所有元素组成的列表（也就是你直觉里的tl xs）分开，剩下的这个尾部列表被直接赋值给了变量xs。

跟着测试用例走一遍递归过程 #

拿你的测试输入number_in_month ([(2018,1,1),(2018,2,2),(2018,2,3),(2018,3,4),(2018,2,30)],2)来举例：

1. 第一次调用：列表不为空，匹配到((2018,1,1) :: xs1, 2)，其中xs1就是[(2018,2,2),(2018,2,3),(2018,3,4),(2018,2,30)]。x2是1，不等于2，所以递归调用number_in_month(xs1, 2)。
2. 第二次调用：匹配到((2018,2,2) :: xs2, 2)，xs2是[(2018,2,3),(2018,3,4),(2018,2,30)]。x2是2，等于m，所以计算1 + number_in_month(xs2, 2)。
3. 第三次调用：匹配到((2018,2,3) :: xs3, 2)，xs3是[(2018,3,4),(2018,2,30)]。x2是2，加1后递归调用number_in_month(xs3, 2)。
4. 第四次调用：匹配到((2018,3,4) :: xs4, 2)，xs4是[(2018,2,30)]。x2是3，不等于2，递归调用number_in_month(xs4, 2)。
5. 第五次调用：匹配到((2018,2,30) :: xs5, 2)，xs5是空列表[]。x2是2，加1后递归调用number_in_month(xs5, 2)。
6. 第六次调用：列表为空，匹配第一个分支，返回0。

然后回溯计算总和：1+1+1+0=3，也就是你得到的结果。

和你直觉里的写法对比 #

你直觉里想传入tl xs，其实完全可以写成那种形式，只是代码会更繁琐：

fun number_in_month (lst, m) = 
  if null lst then 0 
  else 
    let val (_,x2,_) = hd lst 
    in 
      if x2 = m then 1 + number_in_month(tl lst, m) 
      else number_in_month(tl lst, m) 
    end

这段代码和你原来的函数功能完全等价，但模式匹配的写法更简洁、可读性更高，也是SML这类函数式语言的惯用写法——它把“检查列表是否为空”“取头部元素”“取尾部列表”这些操作都整合到了模式匹配里，不用手动调用null、hd、tl。

简单说，不是SML有什么内置遍历机制，而是模式匹配帮你自动提取了列表的尾部，让递归代码更优雅～

内容的提问来源于stack exchange，提问作者147pm