number_in_month练习（列表迭代的SML递归函数）

Question

我在另一个 SO post:

上找到了这段代码

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)

令我惊讶的是它有效。

- number_in_month ([(2018,1,1),(2018,2,2),(2018,2,3),(2018,3,4),(2018,2,30)],2);
val it = 3 : int

我的困惑首先是不熟悉这种形式的经典数学递归函数（我是初学者），然后是它实际上是如何遍历列表的。我的直觉是 if-then-else 中的递归调用发送列表的尾部，即

...
1 + number_in_month((tl xs), m)
...

但这不起作用。每次递归调用如何遍历列表？我只能想象这是某种内置的 SML 魔法。

Answer 1

没有魔法，xs 是列表的尾部。

有两件事需要理解：列表和模式匹配。

在 SML 中，列表语法 [a, b, c] 只是 a :: b :: c :: nil 的 shorthand，其中 :: 是（中缀）cons 构造函数。除了这个 shorthand，SML 中的列表没有什么神奇之处，它们是 pre-defined 这种类型：

datatype 'a list = nil | :: of 'a * 'a list
infixr 5 ::

后一个定义将 :: 变成优先级为 5 的 right-associative 中缀运算符。

其次，定义是在参数上使用模式匹配。像 x::xs 这样的 patten 匹配相同形状的 (non-empty) 列表，将 x 绑定到列表的头部，将 xs 绑定到它的尾部，对应于上面的定义.在您的函数中，x 还被另一个模式本身取代。

就是这样。没有魔法。这同样适用于自定义列表表示：

datatype my_list = empty | cons of (int * int * int) * my_list
infixr 5 cons

fun count (empty, x) = 0
  | count ((_,y,_) cons xs, x) =
    if x = y then 1 + count (xs, x) else count (xs, x)

val test = count ((1,2,3) cons (3,4,5) cons (6,2,7) cons empty, 2)

Answer 2

But how could this be changed to, say, build a new list of matches rather than just counting them?

在这种情况下，您需要对当前解决方案进行两处修改：

您想将递归案例的模式更改为可以提取整个日期三元组（如果匹配）的模式。现在您只提取月份部分进行比较，丢弃其他位，因为您只想增加一个计数器以防月份匹配。
函数的结果不应该是1 + ...，而是(x1,x2,x3) :: ....

快速修复：

fun dates_of_month ([], _) = []
  | dates_of_month ((year,month,day) :: dates, month1) =
    if month = month1
    then (year,month,day) :: dates_of_month (dates, month1)
    else                     dates_of_month (dates, month1)

I changed ...((_,x2,_) :: xs, m) to ...((x1,x2,x3) :: xs, m)... and it worked, but that seems like a kludge.

这里列出了安德烈亚斯·罗斯伯格的两个备选方案：

使用let-in-end:

fun dates_of_month ([], _) = []
  | dates_of_month (date :: dates, month1) =
    let val (_, month, _) = date
    in
      if month = month1
      then date :: dates_of_month (dates, month1)
      else         dates_of_month (dates, month1)
    end

使用as：

fun dates_of_month ([], _) = []
  | dates_of_month ((date as (_,month,_)) :: dates, month1) =
    if month = month1
    then date :: dates_of_month (dates, month1)
    else         dates_of_month (dates, month1)

这里是第三个选项，它通过使用 higher-order 列表组合器抽象出递归：

fun dates_of_month (dates, month1) =
    List.filter (fn (_, month, _) => month = month1) dates

number_in_month练习（列表迭代的SML递归函数）

number_in_month exercise (SML recursive function on list interation)

recursion

list

sml