Simplify this reduce-based idiom

Question
1

I found myself writing the following idiom several times in recent code. It seems like this could be rewritten to something more idiomatic. Can someone help?

The val candidates for comprehension collects a possibly empty collection of values. The if ... expression tests whether the collection is empty and returns the given d else (if not empty) non-destructively appends a reduction of the collection to d .

A problem is that I don’t have a neutral element to give to foldLeft, so I have to call reduce, but I can’t call reduce on an empty collection.

val candidates = for {z <- vertices
                      a <- d.get(x, z)
                      b <- m.get(z, y)
                     } yield semiRingTimes(a, b)

if (candidates.nonEmpty) {
  val newMin: R = candidates.reduce(semiRingPlus)
  d + ((x -> y) -> newMin)
} else {
  d
}
2

If it helps, here is the entire function including types of input parameters.

object SlowShortestPathSemiRing {
  type ADJ[V] = Map[V, Set[V]]
  type MATRIX[V, R] = Map[(V, V), R]

  def computeDistance[V, R](adj: ADJ[V])
                           (semiRingTimes: (R, R) => R, semiRingPlus: (R, R) => R, semiRingTimesIdent: R)
                           (weight: Edge[V] => Option[R]): MATRIX[V, R] = {

    val m: MATRIX[V, R] = for {(src, dsts) <- adj
                               dst <- dsts + src
                               w <- if (src == dst) Some(semiRingTimesIdent) else weight(Edge(src, dst))
                               } yield (src -> dst) -> w
    val vertices = adj.keys
    val n = vertices.size

    (2 until n).foldLeft(m) { (d, k: Int) =>
      vertices.foldLeft(d) { (d, x) =>
        vertices.foldLeft(d) { (d, y) =>
          val candidates = for {z <- vertices
                                a <- d.get(x, z)
                                b <- m.get(z, y)
                                } yield semiRingTimes(a, b)

          if (candidates.nonEmpty) {
            val newMin: R = candidates.reduce(semiRingPlus)
            d + ((x -> y) -> newMin)
          } else {
            d
          }
        }
      }
    }
  }
}
3

You can use reduceOption as a base: From there you can fold:

candidates.reduceOption(semiRingPlus).fold(d)(newMin => d + ((x, y) -> newMin))

or

candidates.reduceOption(semiRingPlus).foldLeft(d)((col, newMin) => col + ((x, y) -> newMin))
1 Like
4

Ahh, so now I understand what reduceOption is for. It appears that it works like reduce but returns None if the container is empty or else Some(reduced-value). Then there is the perverse but useful option.fold. I love it and hate it at the same time.

2 Likes