Data.Map vs Data.IntMap

Posted on February 12, 2014 by Kwang Yul Seo

A map is the one of most widely used data structures in many applications. Thus, many language runtimes provide an efficient implementation of a map. In a purely functional programming language, map is usually implemented as a balanced binary tree. Haskell is no exception here and the implementation of Haskell’s Data.Map is based on size balanced binary trees described in

Data.Map is parameterized over key and value types, so that you can use any type you want as long as key is an instance of Ord type class. So, for example, you can use Int as the key type and store any type you want.

However, Haskell also provides a special version Data.IntMap for Int key. It seems redundant at first, but Data.IntMap is different from Data.Map in that it supports efficient merging of two maps. The implementation of Data.IntMap is described in

The author of Data.IntMap mentions that insertions and deletions of Data.IntMap when compared to a generic size-balanced map implementation are also much faster. This observation suggests that we should use Data.IntMap whenever possible whether or not we need union or intersection of twp maps.