CODEWITHSUNDEEP
listsplitocaml
Redouane Red
Redouane Red

Reputation: 539

Splitting a list using an index

I have a list of integers named t that has an even length n = List.length t. I want to get two lists, the partition of t from index 0 to (n / 2 - 1), and the partition of t from index (n / 2) to (n-1). In other words, I want to split the list t in two parts, but I cannot find anything that does that in the List module (there is List.filter, but it does not filter by index, it takes a function instead).

An example of what I want to do:

let t = [8 ; 66 ; 4 ; 1 ; -2 ; 6  ; 4 ; 1] in
(* Split it to get t1 = [ 8 ; 66 ; 4 ; 1] and t2 = [-2 ; 6 ; 4 ; 1] *)

For now,I have something like this

let rec split t1 t2 n =
match t1 with
| hd :: tl when (List.length tl > n) -> split tl (hd :: t2) n;
| hd :: tl when (List.length tl = n) -> (t1,t2);
| _ -> raise (Failure "Unexpected error");;
let a = [1;2;3;4;7;8];;
let b,c = split a [] (List.length a / 2 - 1);;
List.iter (fun x -> print_int x) b;
print_char '|';
List.iter (fun x -> print_int x) c;

Output is: 478|321, the order has been reversed!

Upvotes: 2

Views: 2187

Answers (1)

Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'

Reputation: 107749

Calculating the length of the list requires walking the list, so it takes time that's linear in the length of the list. Your attempt calculates the length of the remaining list at each step, which makes the total running time quadratic. But you actually don't need to do that! First you calculate the total length of the list. After that, the place to cut is halfway from the beginning, which you can locate by incrementing a counter as you go through the list.

As for the reversal, let's look at what happens to the first element of the list. In the first call to split, the accumulator t2 is the empty list, so h gets put at the end of the list. The next element will be placed before that, and so on. You need to put the first element at the head of the list, so prepend it to the list built by the recursive call.

let rec split_at1 n l =
  if n = 0 then ([], l) else
  match l with
  | [] -> ([], [])    (*or raise an exception, as you wish*)
  | h :: t -> let (l1, l2) = split_at1 (n-1) t in (h :: l1, l2);;
let split_half1 l = split_at1 (List.length l / 2) l;;

This operates in linear time. A potential downside of this implementation is that the recursive call it makes is not a tail call, so it will consume a large amount of stack on large lists. You can fix this by building the first half as an accumulator that's passed to the function. As we saw above, this creates a list in reverse order. So reverse it at the end. This is a common idiom when working with lists.

let rec split_at2 n acc l =
  if n = 0 then (List.rev acc, l) else
  match l with
  | [] -> (List.rev acc, [])
  | h :: t -> split_at2 (n-1) (h :: acc) t;;
let split_half2 l = split_at2 (List.length l / 2) [] l;;

Upvotes: 4

Related Questions