groupBy on List 作为 LinkedHashMap 而不是 Map

Question

我正在使用scala处理XML，并且正在将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

要获得与ListMap中的.groupBy()大致相当的内容，您可以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它。

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(。