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

Question

我是F#的新手,我需要一些F#问题的帮助.

我需要实现一个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移动foward.
• 当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)

注意x::xs步骤1元素,y::y'::ys第二步.

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