在OCaml中拆分列表

Question

我想知道是否有将列表一分为二的选项(或者通常在指定元素处(。

确切地说，我想做这样的事情：有一个列表(例如整数(：

let ml = [1;2;3;4;5]

我想用它做两个列表，长度由第一个列表的参数指定。

它看起来像这样：

let msl1, msl2 = split_at_point ml 3
(* msl1 = [1;2;3], msl2=[4;5] *)

老实说，我真的不在乎分裂是否发生在特定的点上。我所关心的是它会很快并且节省内存(不复制会很好(。我知道，就效率而言，最好的是O(n(，其中n是(结果的(第一个列表的长度。

Answer 1

您无法避免复制列表的前半部分。列表是不可变的，所以获得新列表的唯一方法是从原始列表中复制元素。

列表的后半部分不需要副本，因为列表的尾部是一个列表。

没有内置的函数可以实现这一点(无论如何，在OCaml标准库中(，所以我建议您自己编写。

这看起来很像家庭作业中的内容，所以我只想说，用函数式语言编写大多数列表函数的方法是问问自己，如何使用一个适用于较小输入(通常是列表尾部(的函数来计算原始输入的值。

在你的情况下，你有这样的东西：

let rec split_at_point l n =
if n = 0 then
(* Answer is obvious *)
else
match l with
| [] -> (* Answer is obvious *)
| head :: tail ->
(* Call split_at_point on the tail and
* construct your answer
*)