Balanced reduction algorithm

reduceBalanced.scala

/**
 * Do a 'balanced' reduction of `v`. Provided `f` is associative, this
 * returns the same result as `v.reduceLeft(f)`, but uses a balanced
 * tree of concatenations, which is more efficient for operations that
 * must copy both `A` values to combine them in `f` - O(n*log n) rather than
 * quadratic.
 *
 * Implementation uses a stack that combines the top two elements of the
 * stack using `f` if the top element is more than half the size of the
 * element below it.
 */
def reduceBalanced[A](v: TraversableOnce[A])(size: A => Int)(
                      f: (A,A) => A): A = {
  @annotation.tailrec
  def fixup(stack: List[(A,Int)]): List[(A,Int)] = stack match {
    // h actually appeared first in `v`, followed by `h2`, preserve this order
    case (h2,n) :: (h,m) :: t if n > m/2 =>
      fixup { (f(h, h2), m+n) :: t }
    case _ => stack
  }
  v.foldLeft(List[(A,Int)]())((stack,a) => fixup((a -> size(a)) :: stack))
   .reverse.map(_._1)
   .reduceLeft(f)
}

// examples, using string concatenation with parens to show the grouping we get

scala> reduceBalanced(Vector.range(0,1).map(_.toString))(_.length)((a,b) => s"($a $b)")
res0: String = 0

scala> reduceBalanced(Vector.range(0,2).map(_.toString))(_.length)((a,b) => s"($a $b)")
res1: String = (0 1)

scala> reduceBalanced(Vector.range(0,3).map(_.toString))(_.length)((a,b) => s"($a $b)")
res2: String = ((0 1) 2)

scala> reduceBalanced(Vector.range(0,4).map(_.toString))(_.length)((a,b) => s"($a $b)")
res3: String = ((0 1) (2 3))

scala> reduceBalanced(Vector.range(0,8).map(_.toString))(_.length)((a,b) => s"($a $b)")
res4: String = (((0 1) (2 3)) ((4 5) (6 7)))

scala> reduceBalanced(Vector.range(0,20).map(_.toString))(_.length)((a,b) => s"($a $b)")
res5: String = (((((((0 1) (2 3)) ((4 5) (6 7))) (((8 9) 10) (11 12))) ((13 14) (15 16))) (17 18)) 19)