Convert string to uppercase

Question

I'm programming in SML, trying to take a string and make all the characters capitalized. I'm new to SML and functional programming in general, and I can't quite get the types to match. My code looks like this:

fun allCaps (str) =
  let val ex = explode(str)
    in
      let fun toCaps (acc, nil: char list) = acc
            | toCaps (acc, h::t: char list) = toCaps ((acc::t), [Char.toUpper(h)])
      in
        toCaps(ex, []:char list)
      end
    end;

The interpreter is giving me the error

Error: operator and operand don't agree [tycon mismatch]
  operator domain: char * char list
  operand:         char list * char list
in expression:
  toCaps (acc :: t,Char.toUpper h :: nil)
...
  toCaps (nil: char list,ex)

which makes no sense to me, because it looks very explicit in the function that it is dealing with lists the entire time. Regardless, how do I initialize an empty char type to get the types matching?

Answer 1

trying to take a string and make all the characters capitalized

To convert a string to uppercase,

- val allCaps = String.map Char.toUpper;
- allCaps "Hello World!";
> val it = "HELLO WORLD!" : string

For some general feedback on your code,

• (Logical error) toCaps takes two arguments, (1) the exploded string, and (2) an empty list. But you call the exploded string acc and pattern match against nil/h::t on the empty list; you probably want it the other way around.

• (Type error) You write toCaps ((acc::t), ...), which means putting acc, a list, in front of t, another list. But acc is itself a list of the same kind as t; lists can only contain elements of the same kind, so they can't contain elements of their own type.

• You don't need to nest let-expressions; one let-expression can have multiple declarations:

  fun allCaps s =
    let val L = explode s
        fun toCaps ...
    in ... end
  

• You don't need type annotations unless it improves clarity; the compiler will infer the type.

Converting a string to a list of chars, recursing over that list, and converting the list back to a string, is inefficient but a good learning exercise in list recursion. Here's a revised version of your code:

fun allCaps s =
  let fun upper (c::cs) = Char.toUpper c :: upper cs
        | upper [] = []
  in implode (upper (explode s)) end

This function isn't tail-recursive; for very long strings, upper's calls to itself might eventually exhaust stack memory. You can avoid this by only making tail-calls and by keeping the accumulated result in heap memory by using a function argument as temporary storage:

fun allCaps s =
  let fun upper (c::cs, acc) = upper (cs, Char.toUpper c :: acc)
        | upper ([], acc) = rev acc
  in implode (upper (explode s, [])) end

The drawback is that when you push the first character from c::cs into the front of acc, they end up in reverse order and you need to reverse the result again before imploding it.

Either way, the string-only solution presented at the top uses less memory because it only needs to create a single string the same size as the input and loop over the indices of the input string.