Scala: как объединить коллекцию карт

Question

У меня есть список карт [String, Double], и ​​я хотел бы объединить их содержимое в одну карту [String, Double]. Как я должен сделать это идиоматическим способом? Я полагаю, что я мог бы сделать это со сгибом. Что-то вроде:

val newMap = Map[String, Double]() /: listOfMaps { (accumulator, m) => ... }

Кроме того, я хотел бы обрабатывать столкновения клавиш в общем виде. То есть, если я добавлю ключ к карте, которая уже существует, я смогу указать функцию, которая возвращает Double (в данном случае) и принимает существующее значение для этого ключа плюс значение, которое я пытаюсь добавить , Если ключ еще не существует на карте, просто добавьте его и его значение не измените.

В моем конкретном случае я хотел бы построить одну карту [String, Double], так что если карта уже содержит ключ, то Double будет добавлен к существующему значению карты.

Я работаю с изменяемыми картами в моем конкретном коде, но меня интересуют более общие решения, если это возможно.

Answer 1

Ну, вы могли бы сделать:

mapList reduce (_ ++ _)

за исключением особых требований к столкновению.

Поскольку у вас есть это специальное требование, возможно, лучше всего было бы сделать что-то вроде этого (2.8):

def combine(m1: Map, m2: Map): Map = {
  val k1 = Set(m1.keysIterator.toList: _*)
  val k2 = Set(m2.keysIterator.toList: _*)
  val intersection = k1 & k2

  val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key)))
  val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_)) 
  r2 ++ r1
}

Затем вы можете добавить этот метод в класс карты с помощью шаблона Pimp My Library и использовать его в исходном примере вместо "++":

class CombiningMap(m1: Map[Symbol, Double]) {
  def combine(m2: Map[Symbol, Double]) = {
    val k1 = Set(m1.keysIterator.toList: _*)
    val k2 = Set(m2.keysIterator.toList: _*)
    val intersection = k1 & k2
    val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key)))
    val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_))
    r2 ++ r1
  }
}

// Then use this:
implicit def toCombining(m: Map[Symbol, Double]) = new CombiningMap(m)

// And finish with:
mapList reduce (_ combine _)

Хотя это было написано в 2.8, поэтому keysIterator становится keys для 2.7, filterKeys может потребоваться записать в терминах filter и map, & становится ** и т.д. на это не должно быть слишком по-другому.

Answer 2

Как насчет этого:

def mergeMap[A, B](ms: List[Map[A, B]])(f: (B, B) => B): Map[A, B] =
  (Map[A, B]() /: (for (m <- ms; kv <- m) yield kv)) { (a, kv) =>
    a + (if (a.contains(kv._1)) kv._1 -> f(a(kv._1), kv._2) else kv)
  }

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
val mm = mergeMap(ms)((v1, v2) => v1 + v2)

println(mm) // prints Map(hello -> 5.5, world -> 2.2, goodbye -> 3.3)

И это работает как в 2.7.5, так и в 2.8.0.

Answer 3

Я удивлен, что пока никто не придумал это решение:

myListOfMaps.flatten.toMap

делает именно то, что вам нужно:

1. Объединяет список в одну карту
2. Устраняет дубликаты ключей

Пример:

scala> List(Map('a -> 1), Map('b -> 2), Map('c -> 3), Map('a -> 4, 'b -> 5)).flatten.toMap
res7: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 4, 'b -> 5, 'c -> 3)

flatten превращает список карт в плоский список кортежей, toMap превращает список кортежей в карту со всеми удаленными дублирующимися ключами

Answer 4

Я читаю этот вопрос быстро, поэтому я не уверен, что что-то упустил (например, это должно работать для 2.7.x или без скаляза):

import scalaz._
import Scalaz._
val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms.reduceLeft(_ |+| _)
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2)

Вы можете изменить определение моноида для Double и получить другой способ накапливать значения, получая здесь максимум:

implicit val dbsg: Semigroup[Double] = semigroup((a,b) => math.max(a,b))
ms.reduceLeft(_ |+| _)
// returns Map(goodbye -> 3.3, hello -> 4.4, world -> 2.2)

Answer 5

Я написал сообщение в блоге об этом, зацените его:

http://www.nimrodstech.com/scala-map-merge/

в основном, используя полугруппу скалаза, вы можете достичь этого довольно легко

будет выглядеть что-токак:

  import scalaz.Scalaz._
  listOfMaps reduce(_ |+| _)

Answer 6

Интересно, немного покопавшись, я получил следующее (на 2.7.5):

Общие карты:

   def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: Seq[scala.collection.Map[A,B]]): Map[A, B] = {
    listOfMaps.foldLeft(Map[A, B]()) { (m, s) =>
      Map(
        s.projection.map { pair =>
        if (m contains pair._1)
          (pair._1, collisionFunc(m(pair._1), pair._2))
        else
          pair
      }.force.toList:_*)
    }
  }

Но человек, это отвратительно с проекцией и принуждением, списком и прочее. Отдельный вопрос: как лучше справиться с этим в сгибе?

Для изменчивых Карт, с которыми я имел дело в своем коде, и с менее общим решением, я получил это:

def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A, B] = {
    listOfMaps.foldLeft(mutable.Map[A,B]()) {
      (m, s) =>
      for (k <- s.keys) {
        if (m contains k)
          m(k) = collisionFunc(m(k), s(k))
        else
          m(k) = s(k)
      }
      m
    }
  }

Это выглядит немного чище, но будет работать только с изменяемыми Картами, как написано. Интересно, что сначала я попробовал описанное выше (до того, как задал вопрос), используя /: вместо foldLeft, но я получал ошибки типа. Я думал, что /: и foldLeft были в основном эквивалентны, но компилятор продолжал жаловаться, что мне нужны явные типы для (m, s). Что с этим?

Answer 7

Начиная с Scala 2.13, другое решение, которое обрабатывает дублирующиеся ключи и имеет значение на основе стандартной библиотеки , состоит в объединении Map s в виде последовательностей (flatten) до применение нового groupMapReduce оператора, который (как следует из его названия) является эквивалентом groupBy с последующим отображением и шагом уменьшения сгруппированных значений:

List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
  .flatten
  .groupMapReduce(_._1)(_._2)(_ + _)
// Map("world" -> 2.2, "goodbye" -> 3.3, "hello" -> 5.5)

Это:

• flatten s (объединяет) карты в виде последовательности кортежей (List(("hello", 1.1), ("world", 2.2), ("goodbye", 3.3), ("hello", 4.4))), в которой хранятся все ключи / значения (даже дубликаты ключей)

• group s элементов на основе их первой части кортежа (_._1) (групповая часть group MapReduce)

• map s сгруппированные значения для их второй части кортежа (_._2) (часть карты группы Карта Уменьшение)

• reduce s сопоставили сгруппированные значения (_+_), взяв их сумму (но это может быть любая функция reduce: (T, T) => T) (уменьшить часть groupMap Reduce )

---

Шаг groupMapReduce можно рассматривать как однопроходную версию эквивалент:

list.groupBy(_._1).mapValues(_.map(_._2).reduce(_ + _))

Answer 8

aeliner helper-func, использование которого читается почти так же чисто, как при использовании scalaz:

def mergeMaps[K,V](m1: Map[K,V], m2: Map[K,V])(f: (V,V) => V): Map[K,V] =
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) })

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms.reduceLeft(mergeMaps(_,_)(_ + _))
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2)

для максимальной читабельности оберните его в неявный пользовательский тип:

class MyMap[K,V](m1: Map[K,V]) {
    def merge(m2: Map[K,V])(f: (V,V) => V) =
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) })
}
implicit def toMyMap[K,V](m: Map[K,V]) = new MyMap(m)

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms reduceLeft { _.merge(_)(_ + _) }