how to find number of occurrences in ML string list?

Question

I am new to ML, here is my attemp to writing a function that receives:

• list of strings L
• string str
• int counter

the function should return the number of occurrences of str in L

Here is my code:

(* 
 * return number of occurences of str in L
 * count should be initialized to zero. 
 *)
 fun aux_num_of_occur(L: string list) (str:string) (count:int) =
    if null L then 0
    else if str = hd(L) then
        aux_num_of_occur tl(L) str (count+1)
    else
        aux_num_of_occur tl(L) str count

Those are the errors i got:

Error: case object and rules don't agree [tycon mismatch]
  rule domain: string list * string * int
  object: ('Z list -> 'Z list) * 'Y * 'X
  in expression:
    (case (arg,arg,arg)
      of (L : string list,str : string,count : int) =>
           if null L
           then 0
           else if <exp> = <exp> then <exp> <exp> else <exp> <exp>)

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
             ../compiler/TopLevel/interact/evalloop.sml:44.55
             ../compiler/TopLevel/interact/evalloop.sml:296.17-296.20

My Questions:

1. What is wrong with the syntax?
2. it is not clear to me what the error message says: what is a rule and an object in this case?
3. how can i return a int by recursively calling a function? is it by passing to it a counter as an argument?

Answer 1

This is a classical mistake: tl(L) and tl L are the same thing -- you don't need parentheses for function application in ML-like languages, you just juxtapose the function and the argument(s).

So aux_num_of_occur tl(L) ... is the same thing as aux_num_of_occur tl L ..., i.e. you are trying to apply aux_num_of_occur to the tl function, not to a list of strings. Now, the tl function has type 'a list -> 'a list and that is what you see in the error message (with 'a being 'Z there).

I ought to say that this style with those null, hd, and tl functions is not very idiomatic in SML -- you could use pattern-mathing instead. It is also more convenient to make aux_num_of_occur local to prevent namespace pollution, prevent incorrect usage (you control the initial value of count). Additionally, this gives you the advantage of not passing str all the time when recursing further.

fun num_of_occur ss str =
  let
      fun loop [] count = count
        | loop (s::ss) count =
            if s = str
            then loop ss (count + 1)
            else loop ss count
  in
      loop ss 0
  end

Notice that num_of_occur has a more general type ''a list -> ''a -> int, where ''a means any type with equality comparison. The compiler will generate a warning

Warning: calling polyEqual

which you can either ignore or add some type annotations to num_of_occur. See here for more detail.