number_in_month练习(列表交互的SML递归函数) [英] number_in_month exercise (SML recursive function on list interation)

问题描述

我在另一条 SO 帖子中找到了这段代码:

I found this code on another 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 中的递归调用发送到列表的末尾，即

My confusion is first unfamiliarity with this form of classic mathematical recursive function (I'm a beginner), then how it actually steps through the list. My intuition would have the recursive calls in the if-then-else sending the tail of the list, i.e.,

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

但这不起作用.每次递归调用如何遍历列表?我只能想象这是某种形式的内置SML魔术.

but that doesn't work. How is it iterating through the list with each recursive call? I can only imagine this is baked-in SML magics of some sort.

推荐答案

没有魔术， xs 是列表的结尾.

No magic, xs is the tail of the list.

需要了解两件事:列表和模式匹配.

There are two things to understand: lists and pattern matching.

在SML中，列表语法 [a，b，c] 只是 a :: b :: c :: nil 的简写，其中:: 是(中缀)cons构造函数.除了这个简写之外，SML中的列表没有什么神奇之处，它们是预先定义为这种类型的:

In SML, the list syntax [a, b, c] is just a shorthand for a :: b :: c :: nil, where :: is the (infix) cons constructor. Other than this shorthand, there is nothing magic about lists in SML, they are pre-defined as this type:

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

后面的定义将 :: 转换为优先级为5的右关联中缀运算符.

The latter definition turns :: into a right-associative infix operator of precedence 5.

第二，该定义对参数使用模式匹配.像 x::xs 这样的模式匹配相同形状的(非空)列表，将 x 绑定到列表的头部和 xs>尾部，与上面的定义相对应.在您的函数中， x 进一步被另一个模式本身取代.

Secondly, the definition is using pattern matching on the argument. A patten like x::xs matches a (non-empty) list of the same shape, binding x to the head of the list and xs to its tail, corresponding to the definition above. In your function, x furthermore replaced by another pattern itself.

仅此而已.没魔术这同样适用于自定义列表表示形式:

That's all. No magic. This would equally work with a custom list representation:

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)

这篇关于number_in_month练习(列表交互的SML递归函数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！