Split list into two equal lists in F#

Question

I'm really new to F#, and I need a bit of help with an F# problem.

I need to implement a cut function that splits a list in half so that the output would be...

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

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

I can assume that the length of the list is even.

I'm also expected to define an auxiliary function gencut(n, xs) that cuts xs into two pieces, where n gives the size of the first piece:

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

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

I wouldn't normally ask for exercise help here, but I'm really at a loss as to where to even start. Any help, even if it's just a nudge in the right direction, would help.

Thanks!

Answer 1

Since your list has an even length, and you're cutting it cleanly in half, I recommend the following (psuedocode first):

• Start with two pointers: slow and fast.
• slow steps through the list one element at a time, fast steps two elements at a time.
• slow adds each element to an accumulator variable, while fast moves foward.
• When the fast pointer reaches the end of the list, the slow pointer will have only stepped half the number of elements, so its in the middle of the array.
• Return the elements slow stepped over + the elements remaining. This should be two lists cut neatly in half.

The process above requires one traversal over the list and runs in O(n) time.

Since this is homework, I won't give a complete answer, but just to get you partway started, here's what it takes to cut the list cleanly in half:

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

Note x::xs steps 1 element, y::y'::ys steps two.

This function returns the second half of the list. It is very easy to modify it so it returns the first half of the list as well.

Answer 2

You are looking for list slicing in F#. There was a great answer by @Juliet in this SO Thread: Slice like functionality from a List in F#

Basically it comes down to - this is not built in since there is no constant time index access in F# lists, but you can work around this as detailed. Her approach applied to your problem would yield a (not so efficient but working) solution:

let gencut(n, list) = 
    let firstList = list |> Seq.take n |> Seq.toList
    let secondList = list |> Seq.skip n |> Seq.toList
    (firstList, secondList)