Split list into 2 lists of odd & even positions - SML?

Question

I'm required to write a function that takes a list and splits it into 2 lists. The first list will hold elements in odd position and 2nd list hold elements in even position. Here's my attempt which gives me the following warning:

Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...)

How to improve this?

fun splt (lst: int list) =
    let
      fun splt2 (lst: int list, count: int, lst1: int list, lst2: int list) =
          if null lst
          then []
          else if (count mod 2 = 0)
               then splt2 (tl lst, count+1, hd lst::lst1, lst2)
               else splt2 (tl lst, count+1, lst1, hd lst::lst2)
    in
      splt2 (lst,1,[],[])
    end

Here's a 2nd correct implementation that I found but I'm mainly interested in fixing the 1st one!! I want to split a list into a tupple of odd and even elements

fun split [] = ([], [])   
 | split [x] = ([x], [])  
 | split (x1::x2::xs) = 
           let 
             val (ys, zs) = split xs
           in 
            ((x1::ys), (x2::zs))
          end;

UPDATE: Improvement is just replace

  if null lst then
       [] 

with this:

  if null lst then
    [lst1]@[lst2]

Answer 1

To help get you over the error you are encountering you need to look at the type of the function which you have given

val splt = fn : int list -> 'a list

and ask yourself what does an 'a list hold?

- val foo = "foo"::(splt[1,2,3,4,5]);
val foo = ["foo"] : string list
- val bar = 52::splt[1,2,3,4,5];
val bar = [52] : int list

it can hold anything, but the compiler cannot tell by itself.

Answer 2

Here's some feedback for your code:

• Give the function a proper name, like split or partition. The connotations that I have for those names are: Splitting (or exploding) takes something and returns one list of sub-components (e.g. string → char list), while partitioning takes a list of something and divides into two based on a predicate (e.g. List.partition), but they're not really set in stone.
• Make up some variable names that aren't lst, since this is just an abbreviation of the type - surely redundant when even the type is there. For generic methods, good names can be hard to come by. A lot of ML code uses stuff like xs to imply a generic, plural form.

• Ditch the type annotations; you'll get a polymorphic function that reads more easily:

  fun split input =
      let
        fun split' (xys, count, xs, ys) = ...
      in
        split' (input, 1, [], [])
      end
  

• But really, the version you found online has some advantages: Pattern matching ensures that your lists have the right form before the function body is triggered, which minimizes run-time bugs. The functions hd and tl don't.

• You could optimize the order of the cases slightly; i.e. list the most common case first. The parenthesis around x::xs and y::ys is unnecessary. Also, the two other cases (of one or zero elements) can be combined for brevity, but it doesn't matter much.

  fun split (x1::x2::xs) = 
      let 
        val (ys, zs) = split xs
      in 
        (x1::ys, x2::zs)
      end
    | split rest = (rest, [])   
  

• You could also use case-of instead of let-in-end:

  fun split (x1::x2::xs) =
      (case split xs of
            (ys, zs) => (x1::ys, x2::zs))
    | split rest = (rest, [])
  

• Lastly, you may want to make this function tail-recursive:

  fun split xys =
      let fun split' (x1::x2::xs, ys, zs) = split' (xs, x1::ys, x2::zs)
            | split' (rest, ys, zs) = (rev (rest @ ys), rev zs)
      in
        split' (xys, [], [])
      end