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

Solution 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.

Solution 2

In addition to what Jesper.Reenberg mentioned, I just wanted to mention that a match on a bool for true and false can be replaced with an if-then-else. However, some people consider if-then-else uglier than a case statement

Comments

[Jesper.Reenberg]

True that, I guess i'm one of those people :)

[Sekm]

When I try the top code block, I get compile errors saying 'Error: operator is not a function' - It seems like the case all_except_options(s, x) section can't be separated from the get_substitutions1 (x :: xs, s) block. How can I tell sml that NONE and SOME are cases for what's returned by all_except_options and not cases for get_substitutions?

[Jesper.Reenberg]

You could say that "the fun keyword breaks up the two functions". It works in SML/NJ 110.72, so either you are using another interpreter or you have done something wrong. You could put the nested case expression inside parenthesis. However the error message you are getting, doesn't sound like it has anything to do with the cases?

[Volker Stolz]

There's always room to optimize an "if .. then true else false" :-)

[mat4nier]

@Jesper.Reenberg I know this is an old thread, but I'm trying to puzzle out what is in SOME y in all_except_option. If you switch it to return SOME (x::"wtf"::y) you can see that runs on all elements prior to matching the string, but not on any elements after the string is matched. If y holds the remainder of the list, why don't I see the list duplicated? I'm having a hard time 'stepping' through this problem with a pad of paper and keeping track of what SOME y actually points to at each step.