使用索引拆分列表

Question

我有一个名为t的整数列表，它具有偶数长度的n = List.length t。我想得到两个列表，从索引0到(n /2-1)的t分区和从索引(n / 2)到(n-1)的t分区。换句话说，我想将list t分成两部分，但是在List模块(有List.filter，但它没有按索引过滤，而是使用一个函数)中找不到这样的东西。

我想做的一个例子是：

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

现在，我有这样的事情

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;

输出是：478|321，顺序被颠倒了！

Answer 1

计算列表的长度需要遍历列表，因此在列表的长度中需要线性的时间。您的尝试在每一步计算剩余列表的长度，这使得总运行时间为二次。但你其实不需要这么做！首先计算列表的总长度。之后，切割的位置从开始到一半，您可以通过在列表中增加一个计数器来定位这个位置。

至于反转，让我们来看看列表的第一个元素发生了什么。在对split的第一次调用中，累加器t2是空列表，因此h被放在列表的末尾。下一个元素将放在该元素之前，依此类推。您需要将第一个元素放在列表的开头，因此将其放在递归调用生成的列表的前面。

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;;

这在线性时间内运行。这种实现的一个潜在缺点是它进行的递归调用不是尾调用，因此它将消耗大列表上的大量堆栈。您可以通过将前半部分构建为传递给函数的累加器来修复此问题。正如我们在上面看到的，这创建了一个顺序相反的列表。所以在最后把它倒过来。在处理列表时，这是一个常见的成语。

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;;