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)
}
```