SML: LookSay recursion

user_12871146 0
Viewed 61

I am doing self-study on functional programming and there is no teacher could guide me. Thanks for help me!

(*lookSay:int list=>int*int list
ENSURE: true
REQUIRE: computes the look-and-say sequence, for example list of l=[2,2,2] which would be read as "three twos"  =>[(2,1),(1,2)] *)

here is my code:

    fun lookSay(x:int list)=
    case x of
    []=>[]
      | l::ls =>
    let fun helper(l,l'::ls',acc)=
              if l=l'
              then helper(l,ls',acc+1)
              else (acc,l)::lookSay(ls)
    in
        helper(l,ls,1)
    end

I don't understant why it doesn't work. the solution offered by others is using a helper function runWith(x,L) returns (repeated, tail) : but I don't know how to come out this solution..

    fun runWith (_:int, [] : int list) : int list * int list = ([], [])
  | runWith (x, y::L) =
    if x = y then
      let
        val (repeats, tail) = runWith(x, L)
      in
        (x::repeats, tail)
      end
    else
      ([], y::L)
recursion sml
1 Answers

I'd start off by formatting your solution like this:

fun lookSay [] = []
  | lookSay (x::xs) =
    let
      fun helper(y, z::zs, count) =
          if y = z
          then helper(y, zs, count + 1)
          else (count, y) :: lookSay zs
    in
      helper(x, xs, 1)
    end

I've used x, y and z rather than l and l' because I find that l can be hard to read: I can't easily see if it's a lowercase L, an uppercase i, or a 1. Since we're actually using the constant 1 also, this adds to the confusion.

I've also done some variable renaming: You have one pair of l and ls in the scope of the case-of, and another identically named pair of l and ls inside the helper function that shadow the outer variables. While this works, it is extremely confusing the have different things in close proximity named the same.

Similarly I renamed acc into count to clarify what it accumulates.

As molbdnilo hinted, your problem lies in a missing pattern match. The ML compiler should warn you of this:

! Toplevel input:
! ..........helper(y, z::zs, count) =
!           if y = z
!           then helper(y, zs, count + 1)
!           else (count, y) :: lookSay zs
! Warning: pattern matching is not exhaustive

Which hints that helper should also have a [] pattern.

As for the strategy of this solution: The inner helper function does two things that necessitates an inner helper function. First, it has an extra argument for the "current" item, which I called y, and second, it has the accumulating argument, which I called count. Peculiarly, helper calls lookSay rather than itself.

But only the second of these is truly necessary, since you can also use the head of the list argument to keep the "current" item:

fun lookSay xs =
  let
    fun go [] _ = []
      | go (x::y::zs) count =
        if x = y
        then go (x::zs) (count + 1)
        else (count + 1, x) :: go (y::zs) 0
  in
    go xs 0
  end

This strategy looks at the first two elements of a list at once, x and y, and if they're equal, it discards one but increments count. If x and y are not equal, this marks the end of the sequence of xs, so a (count + 1, x) element is emitted and go can call itself recursively on y::zs.

I've preserved the bug that is also present in your example. In my version molbdnilo's hint can be rephrased as "Think about how the go function handles lists with exactly one element."

I think that to make this function slightly more useful, you want to actually emit a plain list:

fun concatMap f xs =
    List.concat (List.map f xs)

fun flatten pairs =
    concatMap (fn (n, x) => [n, x]) pairs

fun lookSay xs =
  let
    fun go [] _ = []
      | go (x::y::zs) i =
        if x = y
        then go (x::zs) (i+1)
        else (i+1,x) :: go (y::zs) 0
  in flatten (go xs 0) end

Assuming that the bug gets fixed, this should give you:

- lookSay [1, 1, 1, 2, 2, 3];
> val it = [3, 1, 2, 2, 1, 3] : int list
user_2359080
Related