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

在 OCaml 中拆分列表

Splitting a list in OCaml

ocaml

linked-list