count number of chars in String

In SML, how can i count the number of appearences of chars in a String using recursion? Output should be in the form of (char,#AppearenceOfChar). What i managed to do is

    fun frequency(x) = if x = [] then [] else [(hd x,1)]@frequency(tl x)

which will return tupels of the form (char,1). I can too eliminate duplicates in this list, so what i fail to do now is to write a function like

    fun count(s:string,l: (char,int) list)

which 'iterates' trough the string incrementing the particular tupel component. How can i do this recursively? Sorry for noob question but i am new to functional programming but i hope the question is at least understandable :)

Solution

I'd break the problem into two: Increasing the frequency of a single character, and iterating over the characters in a string and inserting each of them. Increasing the frequency depends on whether you have already seen the character before.

fun increaseFrequency (c, []) = [(c, 1)]
  | increaseFrequency (c, ((c1, count)::freqs)) =
      if c = c1
      then (c1, count+1)
      else (c1,count)::increaseFrequency (c, freqs)

This provides a function with the following type declaration:

val increaseFrequency = fn : ''a * (''a * int) list -> (''a * int) list

So given a character and a list of frequencies, it returns an updated list of frequencies where either the character has been inserted with frequency 1, or its existing frequency has been increased by 1, by performing a linear search through each tuple until either the right one is found or the end of the list is met. All other character frequencies are preserved.

The simplest way to iterate over the characters in a string is to explode it into a list of characters and insert each character into an accumulating list of frequencies that starts with the empty list:

fun frequencies s =
    let fun freq [] freqs = freqs
          | freq (c::cs) freqs = freq cs (increaseFrequency (c, freqs))
    in freq (explode s) [] end

But this isn't a very efficient way to iterate a string one character at a time. Alternatively, you can visit each character by indexing without converting to a list:

fun foldrs f e s =
  let val len = size s
      fun loop i e' = if i = len
                      then e'
                      else loop (i+1) (f (String.sub (s, i), e'))
  in loop 0 e end

fun frequencies s = foldrs increaseFrequency [] s

You might also consider using a more efficient representation of sets than lists to reduce the linear-time insertions.