Categories

# 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.

## One reply on “F# Friday – Array.splitAt”

[…] F# Friday â€“ Array.splitAt –Â Brad Collins […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.