list - タプルの2つのリストをマージする方法は？

Question

Scalaに2つのリストがありますが、タプルがグループ化されるようにそれらをマージするにはどうすればよいですか？

これを実行できる既存のScalaリストAPIはありますか、それとも自分で実行する必要がありますか？

入力：

 List((a,4), (b,1), (c,1), (d,1))
 List((a,1), (b,1), (c,1))

期待される出力：

List((a,5),(b,2),(c,2),(d,1))

Answer 1

次の1行を試すことができます。

scala> ( l1 ++ l2 ).groupBy( _._1 ).map( kv => (kv._1, kv._2.map( _._2).sum ) ).toList
res6: List[(Symbol, Int)] = List(('a,5), ('c,2), ('b,2), ('d,1))

マージするタプルのリストはどこl1にありl2ますか。

さて、内訳：

• (l1 ++ l2)両方のリストを連結するだけです
• .groupBy( _._1)すべてのタプルを最初の要素でグループ化します。最初の要素をキーとしてマップと、この要素で始まるタプルのリストを値として受け取ります。
• .map( kv => (kv._1, kv._2.map( _._2).sum ) )同様のキーを使用して新しいマップを作成しますが、値はすべての2番目の要素の合計です。
• .toList結果をリストに戻します。

または、パターンマッチングを使用して、タプル要素にアクセスすることもできます。

( l1 ++ l2 ).groupBy( _._1 ).map{
  case (key,tuples) => (key, tuples.map( _._2).sum ) 
}.toList

Answer 2

mapValuesまたは、コードを短縮するために使用することもできます。

mapValuesおそらくご想像のとおり、 によって作成されたマップ内の各 (キー、値) ペアの値のみを再マップできますgroupBy。

この場合、渡された関数は、mapValues各 (Char, Int) タプルを Int だけに減らし、結果の Int の List を合計します。

(l1 ::: l2).groupBy(_._1).mapValues(_.map(_._2).sum).toList

出力リストの順序が例に従う必要がある場合はsorted、 Ordering[(Char, Int)] 暗黙のインスタンスに依存するものを追加するだけです。

(l1 ::: l2).groupBy(_._1).mapValues(_.map(_._2).sum).toList.sorted

Answer 3

List[(A,B)]両方が に従って順序付けられていると想定できる場合Ordering[A]、次のように記述できます。

def mergeLists[A,B](one:List[(A,B)], two:List[(A,B)])(op:(B,B)=>B)(implicit ord:Ordering[A]): List[(A,B)] = (one,two) match {
    case (xs, Nil) => xs
    case (Nil, ys) => ys
    case((a,b)::xs,(aa,bb)::ys) =>
      if (a == aa) (a, op(b,bb)) :: mergeLists(xs,ys)(op)(ord)
      else if (ord.lt(a,aa)) (a, b) :: mergeLists(xs, (aa,bb)::ys)(op)(ord)
      else (aa, bb) :: mergeLists((a,b) :: xs, ys)(op)(ord)
}

残念ながら、これは末尾再帰ではありません。