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)
and to my surprise it works.
- number_in_month ([(2018,1,1),(2018,2,2),(2018,2,3),(2018,3,4),(2018,2,30)],2);
val it = 3 : int
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)
...
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.
No magic, xs is the tail of the list.
There are two things to understand: lists and pattern matching.
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 ::
The latter definition turns :: into a right-associative infix operator of precedence 5.
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)