Create a repeat function in SML-CodePudding

I am working on creating a function called repeat that takes two int lists lst1 and lst2. Assume that lst2 only has nonnegative integers, repeats the integers in the first list lst1 according to the numbers indicated by the second list lst2. If both lists are empty, return an empty list. You may need a local function.

Example:
repeat ([1,2,3], [4,0,3]) -> [1,1,1,1,3,3,3]

I am having a little trouble with getting started with this function. What should I put after the xs?

fun repeat(lst1, lst2) =
    case lst1 of
      [] => []
    | x::xs' => [] (* what should I put here *)

CodePudding user response：

Like any recursion problem, what's your base case? I'd say in this case it's both lists are empty and it gives you an empty list.

fun repeat([], []) = []

What if one is empty but the other isn't? That's a failure. Let's define an exception we can throw if this happens.

exception MismatchedArguments;

fun repeat([], []) = []
  | repeat([], _) = raise MismatchedArguments
  | repeat(_, []) = raise MismatchedArguments

Now the real question is what we do the rest of the time. Fortunately, SML makes it easy to pattern match both lists and extract their first elements.

exception MismatchedArguments;

fun repeat([], []) = []
  | repeat([], _) = raise MismatchedArguments
  | repeat(_, []) = raise MismatchedArguments
  | repeat(x::xs, y::ys) = ...

At this point, we need a recursive function to repeat an element of the list a certain number of times. As with the overall function, here we see the two hallmarks of recursion: at least one base "exit" condition, and an update step where we converge toward the base condition by updating n to n - 1.

exception MismatchedArguments;

fun repeat([], []) = []
  | repeat([], _) = raise MismatchedArguments
  | repeat(_, []) = raise MismatchedArguments
  | repeat(x::xs, y::ys) = 
      let
        fun repeat'(_, 0) = []
          | repeat'(x, n) = x :: repeat'(x, n - 1)
      in
        ...
      end

Now, we just need to put it all together, by feeding x and y to repeat' and then concatenating that with the result of calling repeat again with xs and ys. By doing this, we converge down toward the base case of repeat([], []) or we may converge toward a mismatched scenario where a MismatchedArguments exception is raised.

exception MismatchedArguments;

fun repeat([], []) = []
  | repeat([], _) = raise MismatchedArguments
  | repeat(_, []) = raise MismatchedArguments
  | repeat(x::xs, y::ys) = 
      let
        fun repeat'(_, 0) = []
          | repeat'(x, n) = x :: repeat'(x, n - 1)
      in
        repeat'(x, y) @ repeat(xs, ys)
      end

Now repeat([1, 2, 3], [4, 0, 3]) will yield [1, 1, 1, 1, 3, 3, 3].