How to reduce with a non-associative function via adjacent pairs

Question

How can I reduce a collection via adjacent pairs?

For instance, let + be a non-associative operator:

(1, 2, 3, 4, 5, 6) => ((1+2) + (3+4)) + (5+6)

(a, b, c, d, e, f, g, h) => ((a+b) + (c+d)) + ((e+f) + (g+h))

This question is similar to this, however I don't think parallel collections apply because the semantics require an associative operator for determinism. I'm not concerned so much about parallel execution as I am about the actually associating such that it constructs a balanced expression tree.

Possibly relevant: [StackOverflowError when operating with a large number of columns in Spark](https://stackoverflow.com/questions/49691021/stackoverflowerror-when-operating-with-a-large-number-of-columns-in-spark/49693374#49693374). There was a problem to reduce over a few thousand of columns, because the abstract syntax tree representing the computation became unbalanced and too deep. — Andrey Tyukin, Jul 06 '18 at 21:30

Andrey Tyukin · Accepted Answer · 2018-07-06T21:20:27.483

Here is a version that does what you want, but treats the "remaining" elements somewhat arbitrarily (if the number of inputs in current iteration is odd, one element is left as-is):

def nonassocPairwiseReduce[A](xs: List[A], op: (A, A) => A): A = {
  xs match {
    case Nil => throw new IllegalArgumentException
    case List(singleElem) => singleElem
    case sthElse => {
      val grouped = sthElse.grouped(2).toList
      val pairwiseOpd = for (g <- grouped) yield {
        g match {
          case List(a, b) => op(a, b)
          case List(x) => x
        }
      }
      nonassocPairwiseReduce(pairwiseOpd, op)
    }
  }
}

For example, if this is your non-associative operation on Strings:

def putInParentheses(a: String, b: String) = s"(${a} + ${b})"

then your examples

for {
  example <- List(
    ('1' to '6').toList.map(_.toString),
    ('a' to 'h').toList.map(_.toString)
  )
} {
  println(nonassocPairwiseReduce(example, putInParentheses))
}

are mapped to

(((1 + 2) + (3 + 4)) + (5 + 6))
(((a + b) + (c + d)) + ((e + f) + (g + h)))

Would be interesting to know why you want to do this.

This is perfect, thanks! I want to do this because I'm using Scala to design hardware (with a library called Chisel), so my non-associative function is creating a particular topology of hardware modules. — Ryan Lorica, Jul 06 '18 at 21:49

How to reduce with a non-associative function via adjacent pairs

1 Answers1