Categories

# Scala Saturday – Vector.splitAt

`Vector.splitAt` splits a vector 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 a vector, i.e., splitting it into two (nearly) equal parts. To do that, half the length, and use it as your splitting index:

```val xs = Vector(1,2,3,4,5,6)
val mid = xs.length / 2 // 3
val (left, right) = xs splitAt mid
// left: Vector[Int] = Vector(1, 2, 3)
// right: Vector[Int] = Vector(4, 5, 6)
```

But what happens if your vector 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` vector will always have one less element than the `right` vector:

```val xs = Vector(1,2,3,4,5)
val mid = xs.length / 2 // 2
val (left, right) = xs splitAt mid
// left: Vector[Int] = Vector(1, 2)
// right: Vector[Int] = Vector(3, 4, 5)
```

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

```val xs = Vector(1,2,3,4,5)
val (left, right) = xs splitAt 1
// left: Vector[Int] = Vector(1)
// right: Vector[Int] = Vector(2, 3, 4, 5)
```

Or …

```val xs = Vector(1,2,3,4,5)
val (left, right) = xs splitAt 4
// left: Vector[Int] = Vector(1, 2, 3, 4)
// right: Vector[Int] = Vector(5)
```

What happens if you split at index 0?

```val xs = Vector(1,2,3,4,5)
val (left, right) = xs splitAt 0
// left: Vector[Int] = Vector()
// right: Vector[Int] = Vector(1, 2, 3, 4, 5)
```

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

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

```val xs = Vector(1,2,3,4,5)
val (left, right) = xs splitAt 5
// left: Vector[Int] = Vector(1, 2, 3, 4, 5)
// right: Vector[Int] = Vector()
```

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

```val xs = Vector(1,2,3,4,5)
val (left, right) = xs splitAt 6
// left: Vector[Int] = Vector(1, 2, 3, 4, 5)
// right: Vector[Int] = Vector()
```

Well, that’s interesting. So then, if you split at any index greater than the length of the input vector, the `left` contains the input vector while the `right` vector is empty.

You get the reverse if you split on a negative number:

```val xs = Vector(1,2,3,4,5)
val (left, right) = xs splitAt -1
// left: Vector[Int] = Vector()
// right: Vector[Int] = Vector(1, 2, 3, 4, 5)
```

### Merge Sort with Vector.splitAt

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

Speaking of which, start by using `Vector.splitAt` to define a `bisect` function that splits a vector in half:

```def bisect[A](xs: Vector[A]) = {
val mid = xs.length / 2
xs splitAt mid
}
```

A merge sort breaks a vector down into single-element (or empty) vectors 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:

```def merge(left: Vector[Int], right: Vector[Int]) = {
@tailrec
def mergeWith(l: Vector[Int], r: Vector[Int], acc: Vector[Int]): Vector[Int] = {
(l.isEmpty, r.isEmpty) match {
// If either side is empty, just add
// the non-empty side to the accumulator.
case (true, _) => acc ++ r
case (_, true) => acc ++ l

// the lesser head value to the
// accumulator. Then call recursively.
case _ =>
val (next, l2, r2) =
if (lh < rh) (lh, l.tail, r)
else (rh, l, r.tail)
mergeWith(l2, r2, acc :+ next)
}
}

mergeWith(left, right, Vector[Int]())
}
```

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

```def mergeSort(as: Vector[Int]): Vector[Int] =
as match {
case Vector() => as
case Vector(a) => as
case _ =>
val (l, r) = bisect(as)
merge(mergeSort(l), mergeSort(r))
}

val xs:  = Vector(43,48,3,23,28,6,25,43,16)
val sorted: Vector[Int] = mergeSort(xs)
// sorted: Vector[Int] =
//   Vector(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 Scala Saturday post for a little while, but I hope to pick back up in a month or two.

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