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

      // Compare the head elements, and add
      // the lesser head value to the
      // accumulator. Then call recursively.
      case _ =>
        val lh = l.head
        val rh = r.head
        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.

Some Examples

Merge Sort with Vector.splitAt

Leave a Reply