在 F# 中将列表拆分为两个相等的列表

我对 F# 确实很陌生，我需要一些关于 F# 问题的帮助。

我需要实现一个剪切函数，将列表分成两半，以便输出......

切[1;2;3;4;5;6];;

val it : int 列表 * int 列表 = ([1; 2; 3], [4; 5; 6])

我可以假设列表的长度是偶数。

我还希望定义一个辅助函数 gencut(n, xs) ，它将 xs 切成两部分，其中 n 给出第一部分的大小：

gencut(2, [1;3;4;2;7;0;9]);;

val it : int 列表 * int 列表 = ([1; 3], [4; 2; 7; 0; 9])

我通常不会在这里寻求锻炼帮助，但我真的不知道从哪里开始。任何帮助，即使只是朝正确方向推动，都会有所帮助。

Thanks!

由于您的列表长度均匀，并且您将其干净地切成两半，因此我建议使用以下内容（首先是伪代码）：

• 从两个指针开始：slow and fast.
• slow一次遍历列表中的一个元素，fast一次步进两个元素。
• slow将每个元素添加到累加器变量中，同时fast向前移动。
• 当。。。的时候fast指针到达链表末尾时，slow指针仅步进了元素数量的一半，因此它位于数组的中间。
• 返回元素slow跨过+剩下的元素。这应该是两个列表，整齐地切成两半。

上述过程需要对列表进行一次遍历，并且运行时间为 O(n)。

由于这是家庭作业，我不会给出完整的答案，但只是为了让您开始一半，以下是将列表彻底削减一半所需的内容：

let cut l =
    let rec cut = function
        | xs, ([] | [_]) -> xs
        | [], _ -> []
        | x::xs, y::y'::ys -> cut (xs, ys)
    cut (l, l)

Note x::xs步骤1元素，y::y'::ys步骤二。

该函数返回列表的后半部分。修改它非常容易，因此它也返回列表的前半部分。