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

Question

我真的是 F# 的新手，我需要一些关于 F# 问题的帮助。

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

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

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

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

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

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

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

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

谢谢!

Answer 1

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

从两个指针开始:slow和 fast .

slow一次遍历列表一个元素，fast一次执行两个元素。

slow将每个元素添加到累加器变量中，而 fast向前移动。

当fast指针到达列表末尾，slow指针只会步进一半的元素，所以它在数组的中间。

返回元素 slow跨过+剩余的元素。这应该是整齐地切成两半的两个列表。

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

由于这是家庭作业，我不会给出完整的答案，但只是为了让您中途开始，以下是将 list 一分为二的方法:

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

备注 x::xs步骤 1 元素， y::y'::ys第二步。

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