Immutable Scala Map implementation that preserves insertion order

Question

LinkedHashMap is used to preserve insertion order in the map, but this only works for mutable maps. Which is the immutable Map implementation that preserves insertion order?

Solution 1

ListMap implements an immutable map using a list-based data structure, and thus preserves insertion order.

scala> import collection.immutable.ListMap
import collection.immutable.ListMap

scala> ListMap(1 -> 2) + (3 -> 4)
res31: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> res31 + (6 -> 9)
res32: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4, 6 -> 9)

The following extension method - Seq#toListMap can be quite useful when working with ListMaps.

scala> import scalaz._, Scalaz._, Liskov._
import scalaz._
import Scalaz._
import Liskov._

scala> :paste
// Entering paste mode (ctrl-D to finish)

implicit def seqW[A](xs: Seq[A]) = new SeqW(xs)
class SeqW[A](xs: Seq[A]) {
  def toListMap[B, C](implicit ev: A <~< (B, C)): ListMap[B, C] = {
    ListMap(co[Seq, A, (B, C)](ev)(xs) : _*)  
  }
}


// Exiting paste mode, now interpreting.

seqW: [A](xs: Seq[A])SeqW[A]
defined class SeqW

scala> Seq((2, 4), (11, 89)).toListMap
res33: scala.collection.immutable.ListMap[Int,Int] = Map(2 -> 4, 11 -> 89)

Solution 2

While ListMap will preserve insertion order, it is not very efficient - e.g. lookup time is linear. I suggest you create a new collection class which wraps both the immutable.HashMap and the immutable.TreeMap. The immutable map should be parametrized as immutable.HashMap[Key, (Value, Long)], where the Long in the tuple gives you the pointer to the corresponding entry in the TreeMap[Long, Key]. You then keep an entry counter on the side. This tree map will sort the entries according to the insertion order.

You implement insertion and lookup in the straightforward way - increment the counter, insert into the hash map and insert to the the counter-key pair into the treemap. You use the hash map for the lookup.

You implement iteration by using the tree map.

To implement remove, you have to remove the key-value pair from the hash map and use the index from the tuple to remove the corresponding entry from the tree map.

Comments

[Eran Medan]

This is not an exact duplicate, the question is for Immutable map, the alleged duplicate is about both mutable and immutable. the other question doesn't directly answer the immutable part (perhaps does indirectly)

[missingfaktor]

+1. Any chance of having such a collection in stdlib in near future?

[axel22]

This hasn't been planned, but if the discussion on the Scala internals mailing list revealed a lot of people want this, then why not.

[axel22]

Would you care to elaborate why?

[AlexG]

Because the index you store in your tuple can change over time when you remove elements from the vector. It's the perfect example of why different collections with different trade-offs exist. Compared to a classic Linked-List map, your implementation lost the ability to remove keys in constant time (log n at best).

[axel22]

Of course. I've edited my answer.

[Matzz]

Using TreeMap will not preserve insertion order. TreeMap sorts keys using comparator.

[axel22]

Read the part of the answer about the TreeMap using Long keys that reflect when an element was inserted. If your comparator is on the insertion order, the tree will preserve the insertion order.

[Tomáš Dvořák]

There's a gotcha with ListMap - calling update() with existing key changes the order of items. Example: ListMap("a" → 1, "b" → 2).updated("a", 2).toList yields List((b,2), (a,2)). Very unfortunate for my use case :(