F# Friday – Array.splitAt

Array.splitAt splits an array into two parts at the index you specify. The first part ends just before the element at the given index; the second part starts with the element at the given index. Some examples will help:

Some Examples

The most obvious use case is bisecting an array, i.e., splitting it into two (nearly) equal parts. To do that, half the length, and use it as your splitting index:

let xs = [|1;2;3;4;5;6|]
let mid = xs.Length / 2 // 3
let left, right = xs |> Array.splitAt mid
// val left : int [] = [|1; 2; 3|]
// val right : int [] = [|4; 5; 6|]

But what happens if your array contains an odd number of elements? No sweat! Because of the way integer division works, the quotient length ÷ 2 is truncated. In other words, the left array will always have one less element than the right array:

let xs = [|1;2;3;4;5|]
let mid = xs.Length / 2 // 2
let left, right = xs |> Array.splitAt mid
// val left : int [] = [|1; 2|]
// val right : int [] = [|3; 4; 5|]

Of course, you don’t have to cut the thing in half. You can split it anywhere:

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 1
// val left : int [] = [|1|]
// val right : int [] = [|2; 3; 4; 5|]

Or …

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 4
// val left : int [] = [|1; 2; 3; 4|]
// val right : int [] = [|5|]

What happens if you split at index 0?

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 0
// val left : int [] = [||]
// val right : int [] = [|1; 2; 3; 4; 5|]

Ah, the left array is empty! That’s because Array.splitAt starts the right array at the given index. There’s nothing before the given index, so the only thing left to return for left is an empty array.

The reverse happens if you split at the length: The right array is empty while the left array contains the entire input array:

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 5
// val left : int [] = [|1; 2; 3; 4; 5|]
// val right : int [] = [||]

But what happens if you try to split at an index greater than the length?

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 6
// System.InvalidOperationException: The input sequence has an insufficient number of elements.
//    at Microsoft.FSharp.Collections.ArrayModule.SplitAt[T](Int32 index, T[] array)
//    at <StartupCode$FSI_0063>.$FSI_0063.main@()

Oops! Well, I guess you shouldn’t do that. So then, just be sure to split at an index that is no greater than the length of the array. You likewise get an exception if you attempt to split at a negative index value.

Merge Sort with Array.splitAt

You can use Array.splitAt in performing a merge sort. Array.splitAt is, admittedly, a pretty small piece of the puzzle. Merge sort is a divide-and-conquer algorithm, and Array.splitAt just performs the divide part. Nevertheless it comes in handy for that part.

Speaking of which, start by using Array.splitAt to define a bisect function that splits an array in half:

let bisect xs =
    let mid = (xs |> Array.length) / 2
    xs |> Array.splitAt mid

A merge sort breaks an array down into single-element (or empty) arrays and then puts them back together, sorting the elements of each block as it combines them. Start with the merge function that puts the blocks back together after you’ve broken them down:

let merge left right =
    let rec mergeWith l r acc =
        match l, r with
        // If either side is empty, just add
        // the non-empty side to the accumulator.
        | ([||], a) | (a, [||]) ->
            Array.append acc a

        // Compare the head elements, and add
        // the lesser head value to the
        // accumulator. Then call recursively.
        | _ ->
            let lh = l |> Array.head
            let rh = r |> Array.head
            let next, l', r' =
                if lh < rh
                then lh, l |> Array.tail, r
                else rh, l, r |> Array.tail
            Array.append acc [|next|]
            |> mergeWith l' r'
        
    [||] |> mergeWith left right

Now mergeSort can use bisect and merge to break down the array and then merge it back together:

let rec mergeSort =
    function
    | [||] -> [||]
    | [|x|] -> [|x|]
    | xs -> 
        let l, r = bisect xs
        merge (mergeSort l) (mergeSort r)
    
let xs = [|43; 48; 3; 23; 28; 6; 25; 43; 16|]
let sorted = mergeSort xs
// val sorted : int [] = 
//   [|3; 6; 16; 23; 25; 28; 43; 43; 48|]

A quick announcement: I’ve got some instructional material to develop. Unfortunately it’s going to take up a fair amount of my time. This is probably the last F# Friday post for a little while, but I hope to pick back up in a month or two.