Split list into two

Question

I would like to implement a function that takes as input a size n and a list. This function will cut the list into two lists, one of size n and the rest in another list. I am new to this language and have a hard time learning the syntax.

The main problem I have is that is finding a way to express a size of the list without using any loops or mutable variables.

Can anyone give a me some pointers?

Answer 1

let split n list =
  let rec not_a_loop xs = function
    | (0, ys) | (_, ([] as ys)) -> (List.rev xs), ys
    | (n, x::ys) -> not_a_loop (x::xs) (n-1, ys)
  not_a_loop [] (n, list)

Answer 2

Let's start with the function's type signature. Since it gets n and a list as arguments and returns a pair of lists, you have a function split:

val split : int -> 'a list -> 'a list * 'a list

Here is one approach to implement this function:

let split n xs =
  let rec splitUtil n xs acc =
    match xs with
    | [] -> List.rev acc, []
    | _ when n = 0 -> List.rev acc, xs
    | x::xs' -> splitUtil (n-1) xs' (x::acc)
  splitUtil n xs []

The idea is using an accumulator acc to hold elements you have traversed and decreasing n a long the way. Because elements are prepended to acc, in the end you have to reverse it to get the correct order.

The function has two base cases to terminate:

• There's no element left to traverse (xs = [] at that point).
• You have gone through the first n elements of the list (n decreases to 0 at that time).

Here is a short illustration of how split computes the result:

   split 2 [1; 2; 3] // call the auxiliary function splitUtil
~> splitUtil 2 [1; 2; 3] [] // match the 3rd case of x::xs'
~> splitUtil 1 [2; 3] [1] // match the 3rd case of x::xs'
~> splitUtil 0 [3] [2; 1] // match the 2nd case of n = 0 (base case)
~> List.rev [2; 1], [3] // call List.rev on acc
~> [1; 2], [3]

Answer 3

New solution - splitAt is now built into List and Array. See commit around 2014 on github. I noticed this today while using F# in VS.2015

Now you can simply do this...

let splitList n list = 
    List.splitAt n list

And as you might expect the signature is...

n: int -> list: 'a list -> 'a list * 'a list

Example usage:

let (firstThree, remainder)  = [1;2;3;4;5] |> (splitList 3)
printfn "firstThree %A" firstThree
printfn "remainder %A" remainder

Output:

firstThree [1; 2; 3]
remainder [4; 5]

Github for those interested: https://github.com/dsyme/visualfsharp/commit/1fc647986f79d20f58978b3980e2da5a1e9b8a7d

Answer 4

One more way, using fold:

let biApply f (a, b) = (f a, f b)

let splitAt n list = 
  let splitter ((xs, ys), n') c =
    if n' < n then
      ((c :: xs, ys), n' + 1)
    else
      ((xs, c :: ys), n' + 1)
  List.fold splitter (([], []), 0) list 
  |> fst 
  |> biApply List.rev

Here is a great series on folds than you can follow to learn more on the topic.