递归遍历 Map 中的值

Question

我正在尝试递归地遍历 Map[String,List[String]] 以提取并展平与 Map

关联的所有值

val x = Map("a" -> List("b","c","d"), "b" -> List("f","g","h"), "f" -> List("i","j","k"), "g" -> List("p","q","r"))

对于每个键，提取值，即列表
对于列表值中的每一项：
- 检查键是否存在然后提取值

递归地继续这样做，直到键没有值并展平键列表的值

结果应该是

Map("a" -> List("b","c","d","f","g","h","i","j","k","p","q","r"), 
    "b" ->  List("f","g","h","i","j","k","p","q","r"), 
    "f" -> List("i","j","k"), 
    "g" -> List("p","q","r"))

Answer 1

试试这个代码：

def f(map: Map[String, List[String]]): Map[String, List[String]] = {
  def f(x: Map[String, List[String]], acc: Map[String, List[String]]): Map[String, List[String]] = {
    if (x.isEmpty) acc
    else {
      val keys = x.keySet
      val (complex, simple) = x partition {_._2 exists {s => keys contains s}}

      val newX =
        (for ((ck, cl) <- complex)
        yield (ck -> (simple.filter(x => cl.contains (x._1)).map(_._2).flatten ++ cl).toList)).toMap

      f(newX, acc ++ simple)
    }
  }

  f(map, Map.empty)
}

val x = Map("a" -> List("b","c","d"), "b" -> List("f", "g", "h"), "f" -> List("i","j","k"), "g" -> List("p","q","r"))

println(f(x)) //Map(f -> List(i, j, k), g -> List(p, q, r), b -> List(i, j, k, p, q, r, f, g, h), a -> List(i, j, k, p, q, r, f, g, h, b, c, d))

但是假设地图中没有递归，例如("a" -> List("b")), ("b" -> List("a")。如果发生这种情况，该函数将以无限循环结束。您将不得不添加额外的代码来处理这种情况。

Answer 2

你可以尝试迭代直到没有变化：

def getValues(dict: Map[String, List[String]]) = Iterator.iterate(dict) { _.mapValues { 
        _.flatMap(v => v :: dict.get(v).toList.flatten).toSet.toList
    } filterNot { _._2.isEmpty }
}.sliding(2) find { x => x.head == x.last }

这绝对不是最有效的解决方案，但它非常简洁！

递归遍历 Map 中的值

Recursively walk values in Map

scala

scala-collections

scala-2.10

scalaz