flatmapping a nested Map in scala-CodePudding

Suppose I have val someMap = Map[String -> Map[String -> String]] defined as such:

val someMap = 
Map( 
    ("a1" -> Map( ("b1" -> "c1"), ("b2" -> "c2") ) ),
    ("a2" -> Map( ("b3" -> "c3"), ("b4" -> "c4") ) ),
    ("a3" -> Map( ("b5" -> "c5"), ("b6" -> "c6") ) )   
)

and I would like to flatten it to something that looks like

List(   
    ("a1","b1","c1"),("a1","b2","c2"),
    ("a2","b3","c3"),("a2","b4","c4"),
    ("a3","b5","c5"),("a3","b6","c6")
)

What is the most efficient way of doing this? I was thinking about creating some helper function that processes each (a_i -> Map(String,String)) key value pair and return

def helper(key: String, values: Map[String -> String]): (String,String,String) 
= {val sublist = values.map(x => (key,x._1,x._2))
return sublist
}

then flatmap this function over someMap. But this seems somewhat unnecessary to my novice scala eyes, so I was wondering if there was a more efficient way to parse this Map.

CodePudding user response：

No need to create helper function just write nested lambda:

val result = someMap.flatMap { case (k, v) => v.map { case (k1, v1) => (k, k1, v1) } }

val y = someMap.flatMap(x => x._2.map(y => (x._1, y._1, y._2)))

CodePudding user response：

Since you're asking about efficiency, the most efficient yet functional approach I can think of is using foldLeft and foldRight.

You need foldRight since :: constructs the immutable list in reverse.

someMap.foldRight(List.empty[(String, String, String)]) { case ((a, m), acc)  =>
  m.foldRight(acc) {
    case ((b, c), acc) => (a, b, c) :: acc
  }
}

Here, assuming Map.iterator.reverse is implemented efficiently, no intermediate collections are created.

Alternatively, you can use foldLeft and then reverse the result:

someMap.foldLeft(List.empty[(String, String, String)]) { case (acc, (a, m))  =>
  m.foldLeft(acc) {
    case (acc, (b, c)) => (a, b, c) :: acc
  }
}.reverse

This way a single intermediate List is created, but you don't rely on the implementation of the reversed iterator (foldLeft uses forward iterator).

Note: one liners, such as someMap.flatMap(x => x._2.map(y => (x._1, y._1, y._2))) are less efficient, as, in addition to the temporary buffer to hold intermediate results of flatMap, they create and discard additional intermediate collections for each inner map.

UPD

Since there seems to be some confusion, I'll clarify what I mean. Here is an implementation of map, flatMap, foldLeft and foldRight from TraversibleLike:

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

  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
  }

  def foldLeft[B](z: B)(op: (B, A) => B): B = {
    var result = z
    this foreach (x => result = op(result, x))
    result
  }

  def foldRight[B](z: B)(op: (A, B) => B): B =
    reversed.foldLeft(z)((x, y) => op(y, x))

It's clear that map and flatMap create intermediate buffer using corresponding builder, while foldLeft and foldRight reuse the same user-supplied accumulator object, and only use iterators.