CODEWITHSUNDEEP
smlsmlnj
zeeks
zeeks

Reputation: 794

Remove real element from list - SML

I have written the following code: 

fun remove_element(nil, elem) = raise Empty
  | remove_element(hd::tl, elem) = if(hd=elem) then tl else hd::remove_element(tl, elem);

but that function (which removed element elem from list) works for int. I need to make it work for real numbers, but I can't do it. I have tried a lot of ways of rewriting the function and also I used :real but these bring me errors.

Any suggestions?

Thank you

Upvotes: 0

Views: 639

Answers (2)

John Coleman
John Coleman

Reputation: 51998

The accepted answer should have allowed you to finish your assignment, so I will show two other approaches for variations of your problem without worrying about doing your homework for you. As Kevin Johnson said, it isn't possible to directly compare two reals. It is possible to do so indirectly since a=b if and only if a<=b and b<=a. Often this is a bug, especially if the list in question is of numbers produced by numerical computations. But -- there are some situations where it makes sense to compare reals for equality so you should certainly be able to do so as long as you are clear that this is what you want. This leads to the following modification of your code:

fun remove_real([],x:real) = []
|   remove_real(y::ys,x) =
        if (y <= x andalso y >= x) then
            remove_real(ys,x)
        else
            y::remove_real(ys,x);

A few points:

1) I changed it to remove all occurrences of the element from the list rather than just the first occurrence. This involved changing the basis case to returning the empty list since [] with y removed is just [] rather than an error situation. Also, rather than simply returning the tail if the element is found I return the recursive call applied to the tail to remove any additional occurrences later on. You could easily modify the code to make it closer to your original code.

2) I needed to put the explicit type annotation x:real so that SML could infer that the list was of type real list rather than type int list.

3) I replaced nil by [] for aesthetic reasons

4) I replaced your pattern hd::tl by y::ys. For one thing, hd and tl are built-in functions -- I see no reason to bind those identifiers to anything else, even if it is just local to a function definition. For another thing, the less visual clutter in a pattern the better.

5) I made more use of white space. Partially a matter of taste, but I think that fairly complicated clauses (like your second line) should be split across multiple lines.

If you want to go the route of including an error tolerance for comparing reals, I think that it makes most sense to include the tolerance as an explicit parameter. I find |x-y| < e to be more natural than two inequalities. Unfortunately, the built-in abs only applies to ints. If x - y is real then the expression

if x - y < 0.0 then y - x else x - y

returns the absolute value of x - y (it flips the sign in the case that it is neagative). As an added bonus -- the comparison with 0.0 rather than 0 is all that SML needs to infer the type. This leads to:

fun remove_elem([],x,tol) = []
|   remove_elem(y::ys,x,tol) =
        if (if x - y < 0.0 then y - x else x - y) < tol then
            remove_elem(ys,x,tol)
        else
            y::remove_elem(ys,x,tol);

Typical output:

- remove_real([2.0, 3.1, 3.14, 3.145, 3.14], 3.14);
val it = [2.0,3.1,3.145] : real list

- remove_elem([2.0, 3.1, 3.14, 3.145, 3.14], 3.14,0.01);
val it = [2.0,3.1] : real list

- remove_elem([2.0, 3.1, 3.14, 3.145, 3.14], 3.14,0.001);
val it = [2.0,3.1,3.145] : real list

Upvotes: 2

Kevin Johnson
Kevin Johnson

Reputation: 1970

The issue is here: hd=elem In languages like ML and Javascript, you cannot directly compare two reals as reals are bound to rounding errors. You have to use a lambda range and define an interval instead. elem - lambda < hd andalso elem + lambda > hd

Upvotes: 2

Related Questions