CODEWITHSUNDEEP
pattern-matchingsml
Square-root
Square-root

Reputation: 883

Pattern matching in SML?

I'm just wondering what is XL variable here, it's not declared anywhere? This function returns NONE if a string is not in the list. Otherwise, returns the original string list but without the string matched.

fun same_string(s1 : string, s2 : string) =
    s1 = s2

fun all_except_option(s1: string, lst: string list) =
    case lst of
         [] => NONE
       | x::xl => if same_string(s1, x)    (* XL HERE ?? *)
                  then SOME xl
                  else case all_except_option(s1, xl) of
                            NONE => NONE
                          | SOME l => SOME (x::l)

Upvotes: 4

Views: 4232

Answers (2)

ruakh
ruakh

Reputation: 183270

As melpomene commented above, the xl on that line actually is the declaration of xl.

In Standard ML, variables are declared (bound) by using patterns that are then matched to values. This is true even when using val; for example, we can write:

val (x, y) = (1, "y")

to declare x (binding it to 1) and y (binding it to "y").

In case expressions and fn expressions, the pattern match also doubles as a conditional; for example, this:

val rec sum =
  fn nil => 0
   | h :: t => h + sum t

creates a function that checks if its argument is nil, in which case it does one thing, vs. if its argument has the form value1 :: value2 (meaning a non-empty list), in which case it does a different thing (using those values). (Hypothetically, if the argument were to have neither of those forms, then the function would end up raising Match; but as it happens, any value of type int list will perforce have one of those two forms, so the function will never raise Match.)

Incidentally, note that that example uses the value identifiers nil and ::, but does not declare them; whereas it does declare the value identifiers h and t. This inconsistency may seem strange; the reason for it is that nil and :: are value constructors, meaning that they've been declared using datatype (datatype 'a list = nil | :: of 'a * 'a list), so they can be used in patterns. Something like this:

val nil = 3

is actually completely illegal, because nil refers to the constructor that's already been declared, and the types of nil and 3 are incompatible. By contrast, if an identifier is not already a value constructor, then appearance in a pattern constitutes a declaration (even if the identifier already is a value variable: the new declaration will simply hide the existing one). This can be a bit tricky for newcomers to the language, but with a little experience you'll find that it makes a lot of sense.

Upvotes: 5

sshine
sshine

Reputation: 16105

That seems like a useful library function. Here are a few pointers on how to improve it:

  1. Don't write your own same_string function that is exactly equivalent to the = operator. Simply use the = operator. Do this because of readability: Other SML programmers will identify the = operator but will wonder if same_string does something more. And why not let the function work for ''a and not just string?

  2. (Minor thing) Don't name your functions after the type they return. The type itself should be sufficient annotation. I.e. you won't accidentally use this function and not realize it's actually returning an 'a list option.

  3. After a while, the following pattern:

    case f x of
     NONE => NONE
   | SOME y => SOME (g y)

    becomes a little tedious and you want to abstract the SOME/NONE part away, since the same thing always happens (either it's a NONE and nothing happens, or it's a SOME y and something happens to the y). Using the library function Option.map with the type ('a → 'b) → 'a option → 'b option:

    Option.map (fn y => g y) (f x)

    It works just like when you map across a list. It might look like:

    fun all_except (_, []) = NONE
  | all_except (x1, x2::xs) =
    if x1 = x2
    then SOME xs
    else Option.map (fn ys => x2::ys) (all_except (x1, xs))

    And you might test it a little crudely like this:

    val test_all_except_1 = all_except (4, [1,2,3]) = NONE
val test_all_except_2 = all_except (1, [1,2,3]) = SOME [2,3]
val test_all_except_3 = all_except (2, [1,2,3]) = SOME [1,3]
val test_all_except_4 = all_except (3, [1,2,3]) = SOME [1,2]
val test_all_except_5 = all_except (1, [1,1,1]) = SOME [1,1]
val test_all_except_6 = all_except (1, [1,2,1]) = SOME [2,1]

  4. You may want to consider writing your functions in curried form:

    fun curry f x y = f (x, y)

fun all_except _ [] = NONE
  | all_except x1 (x2::xs) =
    if x1 = x2
    then SOME xs
    else Option.map (curry op:: x2) (all_except x1 xs)

    Here, all_except takes its two arguments separate from one another, rather than in a (x1, x2::xs) tuple/pair. And the value (fn ys => x2::ys) has been rewritten using the helper function curry in the following steps:

    (fn ys => x2::ys)           (* original *)
(fn ys => op:: (x2, ys))    (* converting :: to a function *)
(fn ys => curry op:: x2 ys) (* making it a curried function *)
(curry op:: x2)             (* performing eta conversion *)

    The last step might seem cryptic. The function curry op:: x2 is the one that takes a list and prepends x2 to it, so it has type 'a list → 'a list. If we temporarily called it f, we'd have (fn ys => f ys), but that's just a silly way of writing f.

Upvotes: 2

Related Questions