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:
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
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|]
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|]
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
mergeSort can use
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.