number_in_month exercise (Why x = x + 1 is considered bool in sml while x is int and how to say x = x + 1 correctly?)

Question

Update: What I want to do with this code is to get a list of dates, year/month/day and a given number as a month, and check to see how many of the dates in the given list are in the same month as that given month. What I meant of x = x + 1 was x++ such as in java or C or C#. As the output I want x. if there is no match, 0 and for any match x = x + 1

So this is my code,

fun number_in_month (Dlist : (int * int * int) list, Month : int, x : int) =
   if null Dlist then x
   else if #2 (hd Dlist) = Month then x = x + 1 andalso number_in_month (tl(Dlist), Month, x)
        else number_in_month ((tl(Dlist)), Month, x)

and it gives me error:

Error: types of if branches do not agree [tycon mismatch]
      then branch: int
      else branch: bool
       in expression:
       if null Dlist
       then x
       else if (fn <rule>) (hd <exp>) = Month
            then (x = <exp> + <exp>)
                  andalso (number_in_month (<exp>,<exp>,<exp>))
            else number_in_month (tl <exp>,Month,x)

I really don't get it why sml is considering x = x + 1 of type bool. I'd be really happy if someone could tell me how can I correctly say x = x + 1 in sml. Thanks a lot in advance.

Answer 1

Saying x = x + 1 in Standard ML, you need to clarify what you intend to say, because clearly x = x + 1 means something you don't intend. What it means is "Compare x with x + 1 and say if they are equal" (which they never will be of any integer).

What I suppose you want to achieve is "update x to its successor", which is not possible without the use of reference types, which I discourage since they are not immutable and functional. The way you usually update something functionally is by passing an updated value to a function that eventually returns it. (Using function arguments as accumulating variables, so it feels as if it's the same variables that update their value e.g. upon each recursive call.)

Another thing I recommend that you do is use pattern matching instead of if-then-else. For example, you know that the list is empty if it matches []. Since the result of your computation is not a boolean, you cannot use "... andalso ..." -- I suspect you do this because you "want to do two things at once, and andalso smells like "doing something and also doing something else", but this would be a misconception. You can do this (using e.g. ; or before), but you would lose your result because these operators deal with side-effects and discard the main effect of one of their operands, so it is not what you want at this point.

Here is my stab in the dark at what you intended, written using pattern matching:

fun number_in_month ([], _, x) = x
  | number_in_month ((one,two,three)::dlist, month, x) =
    if two = month then number_in_month(dlist, month, x+1)
                   else number_in_month(dlist, month, x)

Modified: You can also do this without tail-recursion

fun number_in_month([], _) = 0
  | number_in_month((_,month1,_)::dlist, month2) =
    if month1 = month2 then 1 + number_in_month(dlist, month2)
                       else number_in_month(dlist, month2)

Or written differently:

fun number_in_month([], _) = 0
  | number_in_month((_,month1,_)::dlist, month2) =
    (if month1 = month2 then 1 else 0) + number_in_month(dlist, month2)

Or using list combinators:

fun counter(n1,n2) = if n1 = n2 then 1 else 0
fun number_in_month(dlist, month2) =
    foldl (fn ((_,month1,_),count) => counter(month1,month2) + count) 0 dlist

Or using reference, as you asked for, even though I discourage this:

fun number_in_month (dlist, month2) =
    let val count = ref 0
        fun loop [] = !count (* the value inside the ref-cell *)
          | loop ((_,month1,_)::dlist) =
            if month1 = month2 then (count := !count + 1 ; loop dlist)
                               else loop dlist
    in loop dlist end

As you can see, some complexity is added because I wish to create the ref-cell within the function, but I cannot create a new ref-cell upon every recursive call. So I create a helper function that is recursive and let it have the argument that changes during recursion (it can just inherit month2 and count from the parent scope of number_in_month. When recursion ends (base case), I choose to return the value within the ref-cell (using Standard ML's slightly obscure syntax for dereferencing).

Don't make it a habit of using ref-cells before you master the functional way. Otherwise you are back to coding imperatively in a language that makes this habit ugly. :)