number_in_month练习(列表中的SML递归功能)

Question

我在另一个帖子上找到了此代码：

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 is

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

在SML中，列表语法[a, b, c]只是a :: b :: c :: nil的速记，其中::是(Infix(Cons构造器。除了这个速记外，SML中的列表没有任何魔术，它们被预先定义为这种类型：

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

后一个定义将::变成了优先级的右求和infix操作员5。

其次，定义是在参数上使用模式匹配。像 x::xs这样的patten匹配相同形状的(非空(列表，将 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

但是，如何将其更改为建立新的匹配列表，而不仅仅是计算它们？

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

1. 您想将递归情况的模式更改为一个，如果匹配的话，您可以在其中提取整个日期3键盘。现在，您只是在提取比较的月份部分，扔掉其他位，因为您只想在月份比赛的情况下增加计数器。

2. 该功能的结果不应是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)

我将 ...((_,x2,_) :: xs, m)更改为 ...((x1,x2,x3) :: xs, m)...，它起作用了，但这似乎是一个kludge。

这是安德烈亚斯·罗斯伯格(Andreas Rossberg(的两个替代方法：

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

这是第三个选项，通过使用高阶列表组合来抽象递归：

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