Case Statements and Pattern Matching

Question

I'm coding in SML for an assignment and I've done a few practice problems and I feel like I'm missing something- I feel like I'm using too many case statements. Here's what I'm doing and the problem statements for what I'm having trouble with.:

1. Write a function all_except_option, which takes a string and a string list. Return NONE if the string is not in the list, else return SOME lst where lst is like the argument list except the string is not in it.

   fun all_except_option(str : string, lst : string list) =
     case lst of 
      [] => NONE
     | x::xs => case same_string(x, str) of
                  true => SOME xs
                | false => case all_except_option(str, xs) of
                             NONE => NONE
                           | SOME y=> SOME (x::y)  
   

2. Write a function get_substitutions1, which takes a string list list (a list of list of strings, the substitutions) and a string s and returns a string list. The result has all the strings that are in some list in substitutions that also has s, but s itself should not be in the result.

   fun get_substitutions1(lst : string list list, s : string) = 
     case lst of
       [] => []
     | x::xs => case all_except_option(s, x) of
                    NONE => get_substitutions1(xs, s)
                   | SOME y => y @ get_substitutions1(xs, s)
   

- same_string is a provided function, fun same_string(s1 : string, s2 : string) = s1 = s2

Answer 1

First of all I would start using pattern matching in the function definition instead of having a "top-level" case statement. Its basically boils down to the same thing after de-sugaring. Also I would get rid of the explicit type annotations, unless strictly needed:

fun all_except_option (str, []) = NONE
  | all_except_option (str, x :: xs) =
    case same_string(x, str) of
      true  => SOME xs
    | false => case all_except_option(str, xs) of
                 NONE   => NONE
               | SOME y => SOME (x::y)

fun get_substitutions1 ([], s) = []
  | get_substitutions1 (x :: xs, s) =
    case all_except_option(s, x) of
      NONE   => get_substitutions1(xs, s)
    | SOME y => y @ get_substitutions1(xs, s)

If speed is not of importance, then you could merge the two cases in the first function:

fun all_except_option (str, []) = NONE
  | all_except_option (str, x :: xs) =
    case (same_string(x, str), all_except_option(str, xs)) of
      (true, _)       => SOME xs
    | (false, NONE)   => NONE
    | (false, SOME y) => SOME (x::y)

But since you are using append (@), in the second function, and since it is not tail recursive, I don't believe that it your major concern. Keep in mind that append is potential "evil" and you should almost always use concatenation (and then reverse your result when returning it) and tail recursion when possible (it always is).

If you really like the explicit type annotations, then you could do it like this:

val rec all_except_option : string * string list -> string list option  =
 fn (str, []) => NONE
  | (str, x :: xs) =>
    case (same_string(x, str), all_except_option(str, xs)) of
      (true, _)       => SOME xs
    | (false, NONE)   => NONE
    | (false, SOME y) => SOME (x::y)


val rec get_substitutions1 : string list list * string -> string list =
 fn ([], s) => []
  | (x :: xs, s) =>
    case all_except_option(s, x) of
      NONE   => get_substitutions1(xs, s)
    | SOME y => y @ get_substitutions1(xs, s)

But that is just my preferred way, if I really have to add type annotations.

By the way, why on earth do you have the same_string function? You can just do the comparison directly instead. Using an auxilary function is just wierd, unless you plan to exchange it with some special logic at some point. However your function names doesn't sugest that.