I’ve never really understand the correct way to abstract the type of container. List, Seq, Traversable etc…
I’ve implemented a version of fold/reduce which applies the reduction function using application specific association. For example, given a List such as `(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)’, it groups as follows.
f(f(f(f(zero,1), f(2,3)),
f(f(4,5), f(6,7))),
f(f(f(8,9), f(10,11)),
f(f(12,13), f(14,15)))
There is of course also some special code for handling the remaining elements if the sequence is not of length which is 1 less than a power of 2.
First I wrote the code to work only on a List of objects.
def treeReduce[A](objs: List[A], init: A, f: (A, A) => A): A = {
def recur(stack: List[(Int, A)], remaining: List[A]): A = {
(stack, remaining) match {
case ((i, a1) :: (j, a2) :: tail, _) if i == j => recur((i + 1, f(a1, a2)) :: tail, remaining)
case (_, o :: os) => recur((1, o) :: stack, os)
case ((_, o) :: Nil, Nil) => o
case ((_, a1) :: (_, a2) :: tail, Nil) => recur((0, f(a1, a2)) :: tail, Nil)
}
}
recur((1, init) :: Nil, objs)
}
Next, I wanted to generalize the code to work on any type which foldLeft works on. But I’m not exactly sure how to do that. I can implement the function for Seq[A], but foldLeft seems to be defined on LinearSeqOptimized.
Unless I’m confused, I believe my function will work on any type which implements foldLeft. What is the most general type I could reasonably define treeReduce on?
def treeReduce[A](objs: Seq[A], init: A, f: (A, A) => A): A = {
def consumeStack(stack: List[(Int, A)]): List[(Int, A)] = {
stack match {
case (i, a1) :: (j, a2) :: tail if i == j => consumeStack((i + 1, f(a1, a2)) :: tail)
case _ => stack
}
}
// consume 2^n -1 elements for some n
val stack = objs.foldLeft((1, init) :: Nil) { case (stack: List[(Int, A)], ob: A) =>
(1, ob) :: consumeStack(stack)
}
// there may be up to log_2 of objs.size many pairs left on the stack
assert(stack != Nil)
stack.tail.map(_._2).foldLeft(stack.head._2)(f)
}