ML polymorphic function

Question

I am trying to define a polymorphic function sum over the type T, where type T can be int, real or list of type T. The sum for the case of int and real should work as expected. For the case of list of T, it should return the sum of corresponding elements of two lists (the length of the lists should be same).

Examples:

sum (INT 2, INT 3) = INT 5

sum (REAL 2.3, REAL 3.4) = REAL 5.7

sum(L [2, 3, 4], L [3, 4, 5]) = L [5, 7, 9]

sum(L L([2, 3, 4], [2, 3, 4]), L ([3, 4, 5], [3, 4, 5]) = L ([5, 7, 9], [3, 4, 5])   

The function which I wrote are as follows:

datatype T = INT of int | REAL of real | L of T list;


fun sum (x:T, x':T) = case (x, x') of

  (INT n, INT n') => INT (n + n')

| (REAL n, REAL n') => REAL (n + n')

| (L (x :: xs), L (y :: ys)) => L ((sum (x, y)) :: (sum (L xs, L 
                                                           ys))

| (_,_) => REAL (0.0);

But for the above function I was getting the error:

Constructor applied to the incorrect argument.

expects: _ * [??? list]

but got: _ * [???]

in: :: (sum (x, y), sum (L xs, L ys))

unhandled exception: Fail: compilation aborted: parseAndElaborate reported errors

Hence I changed my code by adding nil as below. As far as I perceived, the reason for the error was the fact that cons operator was trying to concatenate T (INT or REAL) to T (INT or REAL) in the end as (sum (x, y), sum (L xs, L ys)) will eventually get evaluated by recursive call to INT or REAL . Hence I changed my code by adding nil (empty list) in the end

fun sum (x:T, x':T) = case (x, x') of

   (INT n, INT n') => INT (n + n')

 | (REAL n, REAL n') => REAL (n + n')

 | (L (x :: xs), L (y :: ys)) => L ((sum (x, y)) :: (sum (L xs, 
                                                 L ys)) :: nil)

 | (_,_) => REAL (0.0);

But for this case, it behaves correctly for INT and REAL but not for the polymorphic list. It behaves correctly for INT and REAL (as they are simpler to implement). For the list part, I guess there is some problem with the cons operator and am not able to figure out the solution. The test cases which I executed and their outputs are as follows:

sum (L([INT(1)]), L([INT(3)]));
val it = L [INT 4,L []] : T

sum (L([INT(1),INT(2)]), L([INT(3),INT(4)]));
val it = L [INT 4,L [INT #,L #]] : T

P.S: Please ignore the last case (,) => REAL (0.0) as I will handle the case of type mismatch later.

Answer 1

• This seems like a good use-case for mutually recursive functions:

  datatype T = INT of int | REAL of real | L of T list
  
  fun sum (x, x') = case (x, x') of
     (INT  n, INT  n') => INT (n + n')
   | (REAL n, REAL n') => REAL (n + n')
   | (L   ns, L   ns') => L (sumLists (ns, ns'))
   | (_, _)            => ? (* mismatching types *)
  
  and sumLists (x::xs, y::ys) = sum (x, y) :: sumLists (xs, ys)
    | sumLists ([], []) = []
    | sumLists (_, _) = ? (* mismatching lengths *)
  

• Having REAL 0.0 as the result of mismatching types seems like a problem.

  For example, why should sum (INT 2, L [INT 3]) be REAL 0.0?

  And why should sum (INT 2, REAL 3.0) be REAL 0.0?

  Consider either adding an alternate to INT and REAL that has "no value" if that makes sense for your domain, or, probably better, consider changing the sum function to maybe return a sum, if it can meaningfully be computed on all levels of the tree, i.e. val sum : T * T -> T option. It comes down to error handling.

• Write tests that describe the intended behavior of your corner cases. In particular, when it comes to summing values that don't have the same type, and summing lists of mismatching length.

  Your examples would look like this as tests:

  val test1 = sum (L [INT 1], L [INT 3])               = L [INT 4]
  val test2 = sum (L [INT 1, INT 2], L [INT 3, INT 4]) = L [INT 4, INT 6]
  

  Except T isn't an equality type because it contains a real, so you need to write your own equality operator that uses an epsilon test (nearlyEqual) when you encounter a real, for example:

  fun eqT (INT x, INT y) = x = y
    | eqT (REAL x, REAL y) = nearlyEqual(x, y, someEps)
    | eqT (L (x::xs), L (y::ys)) = eqT (x, y) andalso eqT (L ys, L xs)
    | eqT (L [], L []) = true
    | eqT (_, _) = false
  

  Some of your corner cases might look like

  val case1 = sum (INT 2, REAL 3.0)
  val case2 = sum (INT 2, L [])
  val case3 = sum (INT 2, L [INT 3])
  val case4 = sum (L [INT 1], L [INT 1, INT 2])
  val case5 = sum (L [INT 1], L [INT 1, REAL 2.0])
  val case6 = sum (L [], L [L []])