sml

Why does the right-hand-side of clause not agree with function result type?

Starting with this data type defined in SML --

datatype exp = Constant of int
         | Negate of exp
         | Add of exp * exp
         | Multiply of exp * exp

I've written this function which is supposed to list all constants in a given exp:

fun lst_con e = 
        case e of
          Constant i => [i]
        | Negate e2 =>  [~ (lst_con e2)]
        | Add(e1, e2) => [(lst_con e1)] @ [(lst_con e2)]
        | Multiply(e1, e2) => [(lst_con e1)] @ [(lst_con e2)]

However, it is returning this error:

Error: right-hand-side of clause does not agree with function result type [tycon mismatch]    
  expression:  int list    
  result type:  int

I don't understand why. Any explanation would be greatly appreciated!

Solution

  • As molbdnilo has hinted in comments, lst_con is expected to return a list of int values: an int list.

    In your Negate e2 case, you're trying to negative (with ~), a entire list. But op~ expects an int, so the types don't work.

    You also have your first case returning an int list but then the other cases return int list list.

    Additionally, you may be overthinking this. If you have Negate (Constant 42) then negative 42 doesn't exist in that expression as a constant. Only 42 does.

    You probably meant to write something more like:

    fun lst_con e = 
  case e of
    Constant i       => [i]
  | Negate e2        => lst_con e2
  | Add(e1, e2)      => lst_con e1 @ lst_con e2
  | Multiply(e1, e2) => lst_con e1 @ lst_con e2;

    Which we can write more concisely as:

    fun lst_con(Constant i)       => [i]
  | lst_con(Negate e2)        => lst_con e2
  | lst_con(Add(e1, e2))      => lst_con e1 @ lst_con e2
  | lst_con(Multiply(e1, e2)) => lst_con e1 @ lst_con e2;

    Efficiency Issues

    As an additional note, we can see that this function is not tail-recursive, and the use of list append in this way leads to very poor performance characteristics: O(n^2).

    We can achieve this with O(n) runtime performance by using a stack of values left to process and an accumulator.

    fun lst_con'(Constant i, acc, []) = List.rev(i :: acc)
  | lst_con'(Constant i, acc, x::xs) = lst_con'(x, i :: acc, xs)
  | lst_con'(Negate e2, acc, stack) = lst_con'(e2, acc, stack)
  | lst_con'(Add(e1, e2), acc, stack) = lst_con'(e1, acc, e2 :: stack)
  | lst_con'(Multiply(e1, e2), acc, stack) = lst_con'(e1, acc, e2 :: stack);

fun lst_con(e) = lst_con'(e, [], []);

    If we examine how a test case evaluates:

    lst_con(Multiply(Add(Negate(Constant 2), Constant 6), Add(Multiply(Constant 1, Constant 1), Constant 7)))

lst_con'(Multiply(Add(Negate(Constant 2), Constant 6), Add(Multiply(Constant 1, Constant 1), Constant 7)), [], [])

lst_con'(Add(Negate(Constant 2), Constant 6), [], [Add(Multiply(Constant 1, Constant 1), Constant 7)])

lst_con'(Negate(Constant 2), [], [Constant 6, Add(Multiply(Constant 1, Constant 1), Constant 7)]

lst_con'(Constant 2, [], [Constant 6, Add(Multiply(Constant 1, Constant 1), Constant 7)]

lst_con'(Constant 6, [2], [Add(Multiply(Constant 1, Constant 1), Constant 7)]

lst_con'(Add(Multiply(Constant 1, Constant 1), Constant 7), [6, 2], []

lst_con'(Multiply(Constant 1, Constant 1), [6, 2], [Constant 7]

lst_con'(Constant 1, [6, 2], [Constant 1, Constant 7]

lst_con'(Constant 1, [1, 6, 2], [Constant 7]

lst_con'(Constant 7, [1, 1, 6, 2], []

List.rev([7, 1, 1, 6, 2])

[2, 6, 1, 1, 7]