

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

Here's what I've got so far...

fun positive l1 = positive(l1,[],[])
|   positive (l1, p, n) = 
       if hd(l1) < 0
         then positive(tl(l1), p, n @ [hd(l1])
       else if hd(l1) >= 0
         then positive(tl(l1), p @ [hd(l1)], n)
       else if null (h1(l1))
         then p

Yes, this is for my educational purposes. I'm taking an ML class in college and we had to write a program that would return the biggest integer in a list and I want to go above and beyond that to see if I can remove the positives from it as well.

Also, if possible, can anyone point me to a decent ML book or primer? Our class text doesn't explain things well at all.

share|improve this question
up vote 2 down vote accepted

You fail to mention that your code doesn't type.

Your first function clause just has the variable l1, which is used in the recursive. However here it is used as the first element of the triple, which is given as the argument. This doesn't really go hand in hand with the Hindley–Milner type system that SML uses. This is perhaps better seen by the following informal thoughts:

Lets start by assuming that l1 has the type 'a, and thus the function must take arguments of that type and return something unknown 'a -> .... However on the right hand side you create an argument (l1, [], []) which must have the type 'a * 'b list * 'c list. But since it is passed as an argument to the function, that must also mean that 'a is equal to 'a * 'b list * 'c list, which clearly is not the case.

Clearly this was not your original intent. It seems that your intent was to have a function that takes an list as argument, and then at the same time have a recursive helper function, which takes two extra accumulation arguments, namely a list of positive and negative numbers in the original list.

To do this, you at least need to give your helper function another name, such that its definition won't rebind the definition of the original function. Then you have some options, as to which scope this helper function should be in. In general if it doesn't make any sense to be calling this helper function other than from the "main" function, then it should not be places in a scope outside the "main" function. This can be done using a let binding like this:

fun positive xs = 
      fun positive' ys p n = ...
      positive' xs [] [] 

This way the helper function positives' can't be called outside of the positive function.

With this take care of there are some more issues with your original code.

  • Since you are only returning the list of positive integers, there is no need to keep track of the negative ones.

  • You should be using pattern matching to decompose the list elements. This way you eliminate the use of taking the head and tail of the list, and also the need to verify whether there actually is a head and tail in the list.

    fun foo []      = ... (* input list is empty *)
      | foo (x::xs) = ... (* x is now the head, and xs is the tail *)
  • You should not use the append operator (@), whenever you can avoid it (which you always can). The problem is that it has a terrible running time when you have a huge list on the left hand side and a small list on the right hand side (which is often the case for the right hand side, as it is mostly used to append a single element). Thus it should in general be considered bad practice to use it.

    However there exists a very simple solution to this, which is to always concatenate the element in front of the list (constructing the list in reverse order), and then just reversing the list when returning it as the last thing (making it in expected order):

    fun foo [] acc = rev acc
      | foo (x::xs) acc = foo xs (x::acc)

Given these small notes, we end up with a function that looks something like this

fun positive xs =
      fun positive' [] p = rev p
        | positive' (y::ys) p =
          if y < 0 then
            positive' ys p
            positive' ys (y :: p)
      positive' xs []
share|improve this answer

Have you learned about List.filter? It might be appropriate here - it takes a function (which is a predicate) of type 'a -> bool and a list of type 'a list, and returns a list consisting of only the elements for which the predicate evaluates to true. For example:

List.filter (fn x => Real.>= (x, 0.0)) [1.0, 4.5, ~3.4, 42.0, ~9.0]

Your existing code won't work because you're comparing to integers using the intversion of <. The code hd(l1) < 0 will work over a list of int, not a list of real. Numeric literals are not automatically coerced by Standard ML. One must explicitly write 0.0, and use Real.< (hd(l1), 0.0) for your test.

If you don't want to use filter from the standard library, you could consider how one might implement filter yourself. Here's one way:

fun filter f [] = []
  | filter f (h::t) =
      if f h 
      then h :: filter f t 
      else filter f t
share|improve this answer

Your Answer


