Grab first successful pair from a list of maps
You can use find to avoid folding over an entire map, something like:

map1.find {
  case (k, Right(addr1)) =&gt;
    map2.get(k) match {
      case Some(Right(addr2)) =&gt; true
      case _ =&gt; false
    }
  case _ =&gt; false
} match {
  case Some((k, Right(addr1))) =&gt;
    map2.get(k) match {case Some(Right(addr2)) =&gt; Some(haversineDistance(addr1, addr2))}
  case _ =&gt; None
}


(I renamed first/secondAddressOption to map1/map2 to save some typing)

An alternative approach, which doesn't necessarily improve performance but does make the code shorter and more reusable, is to create a method that combines two maps by key:

def combineMaps[K, V](map1: Map[K, V], map2: Map[K, V]): Map[K, List[V]] =
  // To improve performance, compare the sizes of map1 and map2
  // and fold over the smaller map.
  map1.foldLeft(map2.mapValues(List(_))) {
    case (map2, (k, x)) =&gt; map2.updated(k, x :: map2.get(k).toList.flatten)
  }


Then use collectFirst on the combined map:

combineMaps(map1, map2).collectFirst {
  case (_, Right(addr1) :: Right(addr2) :: Nil) =&gt; haversineDistance(addr1, addr2)
}