groupBy в списке как LinkedHashMap вместо карты

Question

Я обрабатываю XML с использованием scala и преобразовываю XML в свои собственные структуры данных. В настоящее время я использую простые Map экземпляры для хранения (под) элементов, однако порядок элементов в XML теряется таким образом, и я не могу воспроизвести исходный XML.

Поэтому я хочу использовать LinkedHashMap экземпляров вместо Map, однако я использую groupBy в списке узлов, который создает Map:

Например:

  def parse(n:Node): Unit = 
  {
    val leaves:Map[String, Seq[XmlItem]] =
      n.child
        .filter(node => { ... })
        .groupBy(_.label)
        .map((tuple:Tuple2[String, Seq[Node]]) =>
        {
          val items = tuple._2.map(node =>
          {
            val attributes = ...

            if (node.text.nonEmpty)
              XmlItem(Some(node.text), attributes)
            else
              XmlItem(None, attributes)
          })

          (tuple._1, items)
        })

      ...
   }

В этом примере я хочу, чтобы leaves имел тип LinkedHashMap, чтобы сохранить порядок n.child. Как мне этого добиться?

Примечание: я группирую по метке / тэгу, потому что элементы могут встречаться несколько раз, и для каждой метки / тэга я сохраняю список элементов в своих структурах данных.

---

Решение
В ответ на @jwvh я использую foldLeft вместо groupBy. Кроме того, я решил пойти с LinkedHashMap вместо ListMap.

  def parse(n:Node): Unit = 
  {
    val leaves:mutable.LinkedHashMap[String, Seq[XmlItem]] =
      n.child
        .filter(node => { ... })
        .foldLeft(mutable.LinkedHashMap.empty[String, Seq[Node]])((m, sn) =>
        {
          m.update(sn.label, m.getOrElse(sn.label, Seq.empty[Node]) ++ Seq(sn))
          m
        })
        .map((tuple:Tuple2[String, Seq[Node]]) =>
        {
          val items = tuple._2.map(node =>
          {
            val attributes = ...

            if (node.text.nonEmpty)
              XmlItem(Some(node.text), attributes)
            else
              XmlItem(None, attributes)
          })

          (tuple._1, items)
        })

Answer 1

Чтобы получить грубый эквивалент .groupBy() в ListMap, вы можете fold над своей коллекцией. Проблема в том, что ListMap сохраняет порядок элементов в том виде, в котором они были добавлены, а не в том виде, в котором они встречались.

import collection.immutable.ListMap

List('a','b','a','c').foldLeft(ListMap.empty[Char,Seq[Char]]){
  case (lm,c) => lm.updated(c, c +: lm.getOrElse(c, Seq()))
}
//res0: ListMap[Char,Seq[Char]] = ListMap(b -> Seq(b), a -> Seq(a, a), c -> Seq(c))

Чтобы это исправить, вы можете foldRight вместо foldLeft. Результатом является исходный порядок элементов при сканировании (сканирование слева направо), но в обратном порядке .

List('a','b','a','c').foldRight(ListMap.empty[Char,Seq[Char]]){
  case (c,lm) => lm.updated(c, c +: lm.getOrElse(c, Seq()))
}
//res1: ListMap[Char,Seq[Char]] = ListMap(c -> Seq(c), b -> Seq(b), a -> Seq(a, a))

Это не обязательно плохо, поскольку ListMap более эффективен с last и init ops, O (1), чем с head и tail ops, O (n ).

Для обработки ListMap в исходном порядке слева направо вы можете .toList и .reverse it.

List('a','b','a','c').foldRight(ListMap.empty[Char,Seq[Char]]){
  case (c,lm) => lm.updated(c, c +: lm.getOrElse(c, Seq()))
}.toList.reverse
//res2: List[(Char, Seq[Char])] = List((a,Seq(a, a)), (b,Seq(b)), (c,Seq(c)))

Answer 2

Чисто неизменное решение будет довольно медленным. Так что я бы пошел с

import collection.mutable.{ArrayBuffer, LinkedHashMap}

implicit class ExtraTraversableOps[A](seq: collection.TraversableOnce[A]) {
  def orderedGroupBy[B](f: A => B): collection.Map[B, collection.Seq[A]] = {
    val map = LinkedHashMap.empty[B, ArrayBuffer[A]]

    for (x <- seq) {
      val key = f(x)
      map.getOrElseUpdate(key, ArrayBuffer.empty) += x
    }

    map
}

Чтобы использовать, просто измените .groupBy в вашем коде на .orderedGroupBy.

Возвращенное Map не может быть изменено с использованием этого типа (хотя его можно привести к mutable.Map или mutable.LinkedHashMap), так что это достаточно безопасно для большинства целей (и вы могли бы создайте ListMap из него в конце, если действительно необходимо).