Map flatten and flatmap not equivalent

问题:

I thought that Scala construct map(f).flatten was equivalent to flatMap(f). But with this example, it is not the case. I wonder what is the role of the case class in it. If I use integers, both are equivalent. But in my case, I cannot.

case class CTest(v: Int)
val s = Set(Map(CTest(0) -> List(0, 3), CTest(1) -> List(0, 2)))
val possibilities = s flatMap { m =>
  val mapping = m flatMap {
    case (label, destNodes) => destNodes map {
      case nodes => (label, nodes) }
  }
  mapping
}
possibilities

Yields

Set((CTest(0),3), (CTest(1), 2))

whereas

case class CTest(v: Int)
val s = Set(Map(CTest(0) -> List(0, 3), CTest(1) -> List(0, 2)))
val possibilities = s flatMap { m =>
  val mapping = m map {
    case (label, destNodes) => destNodes map {
      case nodes => (label, nodes) }
  }
  mapping.flatten
}
possibilities

yields

Set((CTest(0),0), (CTest(0),3), (CTest(1),0), (CTest(1),2))

Any idea why?

回答1:

Take a look at implementation of flatMap:

def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  def builder = bf(repr) // extracted to keep method size under 35 bytes, so that it can be JIT-inlined
  val b = builder
  for (x <- this) b ++= f(x).seq
  b.result
}

Result of flatMap depends on original collection type and result type of function f. In first example you generate sequence of tuples from map, so that compiler picks implementation like CanBuildFrom[Map[A, B], (C, D), Map[C, D]], which provides builder for Map, that causes overwriting of same keys.

You can directly convert map to plain iterable, that will yield result you want:

case class CTest(v: Int)
val s = Set(Map(CTest(0) -> List(0, 3), CTest(1) -> List(0, 2)))
val possibilities = s flatMap { m =>
  val mapping = m.toIterable.flatMap {
    case (label, destNodes) => destNodes map {
      case nodes => (label, nodes) }
  }
  mapping
}
possibilities

回答2:

This happens due to intermediate data structures.

I'll take simple version of your example.

val m = Map(CTest(0) -> List(0, 3), CTest(1) -> List(0, 2))

When using flatMap you directly create a Map[CTest, Int]

scala> m flatMap {
 |     case (label, destNodes) => destNodes map {
 |       case nodes => (label, nodes) }
 |   }
res3: scala.collection.immutable.Map[CTest,Int] = Map(CTest(0) -> 3, CTest(1) -> 2)

In here, due to the uniqueness of the keys of Map, (CTest(0), 0) and (CTest(1), 0) will be dropped from the result. when you flatMap it over set, you will get a Set of Tuples which were in the Map.

In your second example, you map and flatten.

val mapping = m map {
 |     case (label, destNodes) => destNodes map {
 |       case nodes => (label, nodes) }
 |   }
mapping: scala.collection.immutable.Iterable[List[(CTest, Int)]] = List(List((CTest(0),0), (CTest(0),3)), List((CTest(1),0), (CTest(1),2)))

mapping.flatten
res4: scala.collection.immutable.Iterable[(CTest, Int)] = List((CTest(0),0), (CTest(0),3), (CTest(1),0), (CTest(1),2))

There isn't any Map or another uniqueness preserved data structure created in the middle of the process. So values are not dropped.