# Implementing tree-like-fold

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)

}
``````

I tried changing the declaration from

``````def treeReduce[A](objs: Seq[A], init: A, f: (A, A) => A): A
``````

to

``````def treeReduce[A](objs: Traversable[A], init: A, f: (A, A) => A): A
``````

And that works for many situations, but does not work if I try to pass an iterator to `treeReduce`. Which type do I really need for everything that is fold-left-able?