right-hand-side of clause doesn't agree with function result type

Question

Write a function remove_option, which takes a string and a string list. Return NONE if the string　is not in the list, else return SOME xs where xs is identical to the argument list except the string is not　in it. You may assume the string is in the list at most once. Use same_string, provided to you, to　compare strings. Sample solution is around 8 lines.

The function type should be fn : string * string list -> string list option.Here is my code

fun same_string(s1 : string, s2 : string) =
    s1 = s2
fun remove_option (str: string ,str_list : string list) =
    case str_list of 
        [] => NONE
          | x::xs => if same_string(x,str) 
             then SOME xs 
             else x :: remove_option( str,xs)

and the error report

hw2provided.sml:10.5-15.37 Error: right-hand-side of clause doesn't agree with f
unction result type [tycon mismatch]
  expression:  _ option
  result type:  string list
  in declaration:
    remove_option =
      (fn (<pat> : string,<pat> : string list) =>
            (case str_list
              of <pat> => <exp>
               | <pat> => <exp>))

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
             ../compiler/TopLevel/interact/evalloop.sml:44.55
             ../compiler/TopLevel/interact/evalloop.sml:292.17-292.20

So where is the bug ?

Answer 1

The problem is that you want to return a string list option but the line

else x :: remove_option( str,xs)

makes it seem that you want to return a string list

What you need to do with the return value of remove_option( str,xs) is

1) decide what to do if it is NONE

2) extract the string list strings (or whatever you want to call it) if it is of the form SOME strings, tack x onto the front of the list, and repackage it with SOME before returning it.

You seem comfortable with the use of case, so you could use it here.

Answer 2

Since John showed where the bug is, here are some extra comments:

• Since the function same_string is not injected, it is superfluous. You might as well use =.

• Recursive functions that return 'a option are kind of tricky, since you need to unpack the result:

  fun remove_option (s1, []) = NONE
    | remove_option (s1, s2::ss) =
      if s1 = s2
      then SOME ss
      else case remove_option (s1, ss) of
                NONE => NONE
              | SOME ss' => SOME (s2::ss')
  

  Generally, when you see the pattern

  case x_opt of
       NONE => NONE
     | SOME x => SOME (f x))
  

  this can be refactored into using e.g. Option.map : ('a -> 'b) -> 'a option -> 'b option:

  Option.map f x_opt
  

  In this case,

  fun curry f x y = f (x, y)
  
  fun remove_option (s1, []) = NONE
    | remove_option (s1, s2::ss) =
      if s1 = s2
      then SOME ss
      else Option.map (curry op:: s2) (remove_option (s1, ss))
  

  where curry op:: s2, the function that puts s2 in front of a list.