SML: Look and Say Function

Question

I'm having trouble with writing the look and say function recursively. It's supposed to take a list of integers and evaluate to a list of integers that "reads as spoken." For instance,

look_and_say([1, 2, 2]) = "one one two twos" = [1, 1, 2, 2]

and

look_and_say([2, 2, 2]) = "three twos" = [3, 2]

I'm having some difficulty figuring out how to add elements to the list (and keep track of that list) throughout my recursive calls.

Here's an auxiliary function I've written that should be useful:

fun helper(current : int, count : int, remainingList : int list) : int list =
    if (current = hd remainingList) then
        helper(current, count + 1, tl remainingList)
    else
        (* add count number of current to list *)
        helper(hd remainingList, 1, tl remainingList);

And here's a rough outline for my main function:

fun look_and_say(x::y : int list) : int list =
    if x = nil then
    (* print *)
    else
        helper(x, 1, y);

Thoughts?

Answer 1

You seem to have the right idea, although it doesn't look as if your helper will ever terminate. Here's a way of implementing it without a helper.

fun look_and_say [] = []
  | look_and_say (x::xs) =
      case look_and_say xs of
        [] => [1,x]
      | a::b::L => if x=b then (a+1)::b::L 
                   else 1::x::a::b::L

And here's a way of implementing it with your helper.

fun helper(current, count, remainingList) =
  if remainingList = [] then
    [count, current]
  else if current = hd remainingList then
    helper(current, count + 1, tl remainingList)
  else count::current::look_and_say(remainingList)
and look_and_say [] = []
  | look_and_say (x::y) = helper(x, 1, y)