Scala - 通过共同元素合并两个元组列表

Question

如何合并两个模拟 Chasles' 关系的元组列表？

（a, b), (b, c) => (a, c)

以下是一个示例：

val l1 = List(("Dan", "b"), ("Dan","a"), ("Bart", "c"))
val l2 = List(("a", "1"), ("c", "1"), ("b", "3"), ("a", "2"))

期望的结果应该是：

val result = List(("Dan", "3"), ("Dan", "1"), ("Dan", "2"), ("Bart", "1"))

- Dadou

---

你目前尝试了什么？ - hoyland

l1中有时候也会比l2多元素吗？ - Dennis Hunziker

Answer 1

你需要考虑第一个列表中的一个元素和第二个列表中的一个元素组成的所有情况，然后筛选出那些“b”元素匹配的情况。

换句话说，我们要对l1进行映射，并在其中嵌套对l2的映射，也就是说我们要考虑两个列表中各自的元素组成的所有对，具体类似于：

l1.map(x => l2.map(y => (x,y))

但这并不完全正确，因为现在我们有了一个List[List[((String, String),(String,String))]]-- 我们需要使用 flatmap:

l1.flatMap(x => l2.map(y => (x,y)))

现在我们需要筛选出我们想要的配对并整理一下：

l1.flatMap(x => l2.map(y => (x,y)))
  .filter{ case ((_,y),(b,_)) => y == b }
  .map {case ((x, _),(_,c)) => (x,c) }

这为我们提供了

List((Dan,3), (Dan,1), (Dan,2), (Bart,1))

这有点丑陋，我们可以稍微整理一下--在原始的flatmap中过滤l2并在那里构建结果，这样我们就不必操纵元组了：

l1.map{ case (x,y) => 
    l2.filter{ case (b, _) => y == b}
      .map{ case (_, c) => (x, c)} }

这是一个更容易理解的例子，可以使用for循环：

for {
  (x, y) <- l1
  (b, c) <- l2
  if y == b
} yield (x,c)

- hoyland

---

不错的方法，我之前没有这样看过这个问题。谢谢你。 - Dadou

Answer 2

对于 l1 中的每个元组，您可以过滤 l2 以选择具有匹配第一个元素的元组：

def join[A, B, C](l1: List[(A, B)], l2: List[(B, C)]): List[(A, C)] = {
  for {
    (key, subkey) <- l1
    value <- l2.collect { case (`subkey`, value) => value }
  } yield key -> value  
}

你可以事先将l2转换为Map，以提高选择性能：

def join[A, B, C](l1: List[(A, B)], l2: List[(B, C)]): List[(A, C)] = {
  val valuesMap = l2.groupBy(_._1)
  for {
    (key, subkey) <- l1
    (_, value) <- valuesMap.getOrElse(subkey, Nil)
  } yield key -> value  
}

- Kolmar