Trying to write a function in SML

Question

I am trying to write a function in sml that takes a list as its first argument and a number as its second. The result should be: greaterT [3,5,2,4,7]3; val it = [5,4,7] : int list

This is my work so far but doesn't work yet.

fun greaterT ([],k) = []
|   greaterT (a::x,k)
if a <= k
then x = [] 
else greaterT(x,k);

Getting errors when running it in SML of new jersey,Errors types of if branches do not agree then branch: bool else branch: Z list in expression if a <= k then x = [] else greaterT(x,k); — user1732558

Ionuț G. Stan Ionuț G. Stan · Accepted Answer · 2015-03-12T14:56:32

You are getting into problems because the then branch of the if expression is trying to do something which doesn't make sense:

x = []

You can't re-assign values to already bound identifiers in Standard ML, although you can achieve mutability using refs, but they're not needed in this case.

In your case, what the required function conceptually does, is to look at the first element of a list, decide whether to keep it in the final result by comparing it with k and then recurse on the rest of list:

fun greaterT ([], k) = []
  | greaterT (a :: rest, k) =
      if a <= k then
        a :: greaterT (rest, k)
      else
        greaterT (rest, k)

The above isn't a good solution, though, because the first recursive call isn't in a tail position, so the compiler can't optimize the generated code (for reasons I won't discuss here; there are plenty of questions about tail-call optimizations on StackOverflow).

So, a better version would use an extra parameter in which it accumulates elements that satisfy the <= predicate.

fun greaterTailRec ([], k, result) = List.rev result
  | greaterTailRec (a :: rest, k) =
      if a <= k then
        greaterTailRec (rest, k, result)
      else
        greaterTailRec (rest, k, a :: result)

fun greaterT (list, k) = greaterTailRec (list, k, [])

We can go a step further and generalize greaterTailRec by replacing the specifics, which in this particular case is the comparison call <=, to a more general call to a function that takes an element of the list as argument and returns a bool. Thus, we'll end up with a generally useful function called filter:

fun filter predicate list =
  let
    fun recur ([], result) = List.rev result
      | recur (a :: rest, result) =
          if predicate a then
            recur (rest, a :: result)
          else
            recur (rest, result)
  in
    recur (list, [])
  end

fun greaterT (list, k) =
  filter (fn a => a >= k) list

The filter helper function is already defined on the List structure, so your initial function can be more concisely expressed as:

fun greaterT (list, k) =
  List.filter (fn a => a >= k) list

Trying to write a function in SML

1 Answers