CODEWITHSUNDEEP
scala
Ryan Lorica
Ryan Lorica

Reputation: 47

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

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.

Upvotes: 2

Views: 180

Answers (1)

Andrey Tyukin
Andrey Tyukin

Reputation: 44918

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.

Upvotes: 2

Related Questions