Empty list even after appending Standard ML-CodePudding

I have a function that takes in a list and then puts elements into two different lists based on a condition. However, when I check the returned lists they are always empty. Why is this happening?

fun divide_list(l1: type list): (type list, type list) = 
  let
    val count = ref 0 
    and list1 = nil 
    and list2 = nil
  in
    while !count <> 8 do (
      if !count % 2 = 0 then 
        list1 @ [List.nth(l1, !count)]
      else 
        list2 @ [List.nth(l1, !count)];
      count := !count   1
    );
    (list1, list2)
  end

The output I get after running this is as follows:

val it = ([],[]) : type list * type list

CodePudding user response：

You're not modifying the lists, you're creating new lists that are discarded. In order to achieve what you want, you'd need to also wrap the lists in references: and list1 = ref [] and list2 = ref []. Then, at each instance where you intend to modify them, you use := (as you have for modifying the count). Note that you'd rewrite the tuple you're returning to fetch the value held by each reference as well: (!list1, !list2).

As a sidenote, it is regrettable that Standard ML does not inform you of this. In OCaml, for example, the typing rule for sequencing expressions e ; e' ensures e evaluates to () : unit due to the way it's desugared (let () = e in e'). So, the OCaml analogue to your code wouldn't even typecheck.

I would dispense with the ref based solution entirely and do something using a fold, carrying the index:

fun divide xs =
  let
    fun choose (x, ((l, r), i)) =
      (if i mod 2 = 0 then (x :: l, r) else (l, x :: r), i   1)
    
    val (l, r) =
      #1 (List.foldl choose (([], []), 0) xs)
  in
    (List.rev l, List.rev r)
  end

I build up the list partitions backwards and then reverse at the end to avoid quadratic blowup of appending to the end for every element. If you wish to have the length of 8 constraint, then you can combine the usage of the above function with List.take from the basis library.

CodePudding user response：

@contificate has offered a good explanation. You're implementing a list partitioning function. But there's no reason not to factor out the function that will decide how to partition the list. This function only needs to take in a value and return a boolean value.

This is easily implemented in terms of a fold. There is no need, from what I can see, to keep track of the index.

fun partition f lst =
  let
    val (a, b) = List.foldl (fn (x, (a, b)) => if f x then (x::a, b) else (a, x::b)) ([], []) lst
  in
    (List.rev a, List.rev b)
  end;

partition (fn x => x mod 2 = 0) [1, 2, 3, 4, 5];

Yields:

([2, 4], [1, 3, 5])