SML: Type inference giving strange error whilst appending an item to a list

Question

I am trying to reverse a list in SML with the following implementation

 fun reverse x y =
      case x of
         [] => y
       | x::xs => reverse(xs, x::y)
 ;

The error messages I get is impenetrable:

trial.sml:1.6-4.35 Error: case object and rules don't agree [tycon mismatch]
  rule domain: 'Z list * 'Z list
  object: ('Z list * 'Z list) * 'Y
  in expression:
    (case (arg,arg)
      of (x,y) =>
           (case x
             of nil => y
              | :: <pat> => reverse <exp>))
trial.sml:1.6-4.35 Error: right-hand-side of clause doesn't agree with function result type [tycon mismatch]
  expression:  'Z -> _
  result type:  'Y list
  in declaration:
    reverse = (fn arg => (fn <pat> => <exp>))

However if I change the signature to be fun reverse(x: 'a list, y: 'a list) then it works why is this so? Is there a way to write this so that I dont need to have to write the type 'a list ?

John Coleman John Coleman · Accepted Answer · 2017-01-15T17:04:05

x y differs from (x,y).

In the first line of the definition

fun reverse x y =

You seem to be trying to write a curried function of type

fn: a' list -> a' list -> 'a list

but in the recursive call

reverse(xs, x::y)

you are treating reverse as if it were and uncurried function of type

fn: a' list * a' list -> 'a list

The problem has nothing at all to do with whether or not you add a type annotation but instead it has to do with where you put parenthesis (and commas, if any). There are two valid fixes depending on what you want the type to be. Since this seems to be homework (there is no obvious non-homework reason to avoid the built-in rev), I'll leave the details to you.

SML: Type inference giving strange error whilst appending an item to a list

1 Answers