Scala Map Reduction and Aggregation

Question

I have a Map that looks like this and is of Type Map[String, Seq[String]]

Map(
 "5" -> Seq("5.1"),
 "5.1" -> Seq("5.1.1", "5.1.2"),
 "5.1.1" -> Seq("5.1.1.1"),
 "5.1.2" -> Seq.empty[String],
 "5.1.1.1" -> Seq.empty[String]
)

Given a key, I would like to fetch all the values recursively that belongs to the given key. Say for example., if I want to look up for the key 5, I expect the result to be:

Given Input is: 5
Expected Output is: Seq(5.1, 5.1.1, 5.1.2, 5.1.1.1)

Here is what I tried so far:

def fetchSequence(inputId: String, acc: Seq[String], seqMap: Map[String, Seq[String]]): Seq[String] = seqMap.get(inputId) match {
  case None => acc
  case Some(subSeq) =>
    val newAcc = acc ++ subSeq
    subSeq.collect {
      case subId=> fetchSequence(subId, newAcc, seqMap)
    }.flatten
}

I get an empty result when I call fetchSequence with the Map that I have above.

Peter Neyens Peter Neyens · Accepted Answer · 2016-06-29T16:35:33

Somewhat more concise :

def recGet[A](map: Map[A, Seq[A]])(key: A): Seq[A] = 
  map.get(key).fold(
    // return empty Seq if key not found
    Seq.empty[A])(
    // return a Seq with 
    //   the key and 
    //   the result of recGet called recursively 
    //      (for all the elements in the Seq[A] found for key)
    x => Seq(key) ++ x.flatMap(recGet(map)))

You can use recGet as :

val sections = Map(
  "5" -> Seq("5.1"),
  "5.1" -> Seq("5.1.1", "5.1.2"),
  "5.1.1" -> Seq("5.1.1.1"),
  "5.1.2" -> Seq.empty[String],
  "5.1.1.1" -> Seq.empty[String]
)

recGet(sections)("5")      // Seq[String] = List(5, 5.1, 5.1.1, 5.1.1.1, 5.1.2)
recGet(sections)("5.1.1")  // Seq[String] = List(5.1.1, 5.1.1.1)
recGet(sections)("5.2")    // Seq[String] = List()

This will also give you the (first) element itself (if it exists in the map), if you don't want that, you can probably wrap recGet in another method which uses drop(1) on the result of recGet.

Scala Map Reduction and Aggregation

1 Answers