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.

Those aren't test cases. Test cases compare an expected value against an actual value. You haven't said how or why they don't work, so one can only help you by guessing at what you think the mistake is. — sshine, Jun 14 '18 at 10:41
It has become less clear: There is no question. Your tests don't work (`L L([2, 3, 4]` should probably be `L [L [2, 3, 4]]` and you can't compare reals for equality; did you actually read my answer?). And since you edited your main piece of code, you have no base case for the recursion on the `L` pattern, which makes it prettier but more broken than before you edited it. StackOverflow doesn't lend itself very well to the forth-and-back process of gradually ironing out the error messages; you probably need either a tutor or patience for this. — sshine, Jun 15 '18 at 07:08

sshine · Answer 1 · 2018-06-15T07:25:36.787

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 []])

ML polymorphic function

1 Answers1