user1819676 user1819676 - 1 month ago 8
Scala Question

Does scala.collection.Seq.groupBy() function preserve the order?

I'm trying to figure out:


  1. If
    scala.collection.Seq.groupBy()
    preservers the order. Meaning if I have
    List((true, 2), (true, 8))
    , and do groupBy by the first element which is the boolean, will I always end up with a list for true which has 2 before 8.

  2. Same question for toMap. Meaning if I do a toMap on the mentioned list, will I always end up having 8 for the key true, cause 8 comes after 2 and overrides it?



I could not find anything about the implementation in the scala doc: scala doc. I'm trying to decide whether write my own version of it to make sure the order is preserved.

Thanks!

Answer

The implementations use for-comprehensions, which means yes they do preserve order if used in combination with an ordered collection such as Seq:

toMap

def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] = {
  val b = immutable.Map.newBuilder[T, U]
  for (x <- self)
    b += x

  b.result()
}

groupBy

def groupBy[K](f: A => K): immutable.Map[K, Repr] = {
  val m = mutable.Map.empty[K, Builder[A, Repr]]
  for (elem <- this) {
    val key = f(elem)
    val bldr = m.getOrElseUpdate(key, newBuilder)
    bldr += elem
  }
  val b = immutable.Map.newBuilder[K, Repr]
  for ((k, v) <- m)
    b += ((k, v.result))

  b.result
}

However since you noted that this behavior is not documented I'd consider it an implementation detail which can change and subsequently break your code in the future (note that the implementations sit in TraversableLike and TraversableOnce - traversable does not indicate ordering of any kind by itself). Writing your own implementations (or just copying the existing implementations) is future proof.