CODEWITHSUNDEEP
listfunctional-programmingappendsml
Abdul9401
Abdul9401

Reputation: 37

Empty list even after appending Standard ML

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

Upvotes: 0

Views: 182

Answers (2)

Chris
Chris

Reputation: 36611

@contificate has offered a good explanation.

If you're implementing a list partitioning function.

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])

If you simply want to split based on index

If we're aiming to split a list into two lists based on the index:

[4, 7, 1, 9, 8]

Becomes:

([4, 1, 8], [7, 9])

That can be done entirely functionally as well with simple pattern matching and recursion.

let rec split lst (acc1, acc2) =
  match lst with
  | [] -> (acc1, acc2)
  ...

Here we're passing in the list to split, and an accumulator with the two lists. Obviously, if the list is empty, the result is just the accumulator. What if there's one element in the list?

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (acc1, acc2)
  | [x] -> (x::acc1, acc2)
  ...

Well, that goes in the first list. What if there are more elements than one?

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (acc1, acc2)
  | [x] -> (x::acc1, acc2)
  | x::y::tail -> split tail (x::acc1, y::acc2)

Well, then we match the first two elements and the tail. We update the accumulator to place the first two elements in their respective lists, and call split again with the tail and that updated accumulator.

utop # split [4; 7; 1; 9; 8] ([], []);;
- : int list * int list = ([8; 1; 4], [9; 7])

Oops. They're backwards because of how we constructed the accumulators. We can use List.rev to fix this, but because we don't want to do it twice, when there's one element we'll call split on an empty list.

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (List.rev acc1, List.rev acc2)
  | [x] -> split [] (x::acc1, acc2)
  | x::y::tail -> split tail (x::acc1, y::acc2)

utop # split [4; 7; 1; 9; 8] ([], []);;
- : int list * int list = ([4; 1; 8], [7; 9])

And finally you can shadow split to remove the need to explicitly pass the tuple of empty lists.

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (List.rev acc1, List.rev acc2)
  | [x] -> split [] (x::acc1, acc2)
  | x::y::tail -> split tail (x::acc1, y::acc2)

let split lst = split lst ([], [])

Upvotes: 2

Colin James
Colin James

Reputation: 736

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.

Upvotes: 4

Related Questions