Cut a list by index n in F#

Question

Trying to write a recursive function that will cut a list by n. Then return 2 lists. So if I pass

cut(2, [5;10;4;2;7]);;
  val it : int list * int list = ([5; 10], [4; 2; 7])

I would like to get something like that.

let rec cut (n, xs) = 
        match n, xs with 
        | 0, xt -> (n, xs)
        | n, x::xt -> cut(n, xt), xs;;

Please help.

Answer 1

I'll ad an explanation of @MisterMetaphors recursive function.

The cut function isn't recursive but aux is, it works by counting down from n and removing elements from the head of the list passed to cut.

Say you call cut like this cut 2 [ 3; 4; 5; 7; 8 ]. aux is a pattern matching function taking three arguments: n, partition 1, partition 2. Partition 1 starts out with being an empty list and partition 2 starts out with being the full list passed to cut.

First time aux will match the second clause, then it'll call itself with arguments (1, [3], [4; 5; 7; 8]). Next time it'll also match second clause, now it calls itself with (0, [4; 3], [5; 7; 8]). Third and final time it matches first clause (n=0) and it will return a tuple containing xs and ys.

Notice however that the elements of the xs is in reverse order since each element was prepended (using cons operator ::). The reason this is done is because it's an O(1) operation compared to the append operator @ which is O(n) on the left side.

Since xs is in reverse order the last expression in the function is a reversal of xs.

An alternative and slightly short definition could be:

let cut n xs =
    let rec aux = function
        | 0, xs, ys -> List.rev xs, ys
        | n, xs, y :: ys -> aux (n - 1, y :: xs, ys)
        | _ -> failwith "invalid arguments"
    aux (n, [], xs)

Answer 2

It's probably better to combine built-in functions on lists or sequences to achieve this:

let cut' (n, xs) =
    Seq.take n xs, Seq.skip n xs

Recursively, your function can be defined like so:

let cut (n, xs) =
    let rec aux = function
        | 0, xs, ys -> xs, ys
        | n, xs, y :: ys -> aux (n - 1, y :: xs, ys)
        | _ -> failwith "invalid arguments"
    let l, r = aux (n, [], xs)
    (List.rev l, r)