What is the main difference between Data.Sequence / Seq a and Data.IntMap / IntMap a in Haskell? From everything I've read, they both offer a fast cons function, fast random access, and fast random update. What's the difference?
For context, I need all of these (fast cons, fast random access, and fast random update).
Which should I choose?
A Seq stores something for every index between 0 and some number. An IntMap stores something for some but not all Int values. This is a big conceptual difference with obvious consequences for space usage—if your data are sparse, you probably don't want a dense representation. Cons and snoc are somewhat cheaper for Seq than for IntMap, I'd expect, though they have different meanings, while random access is significantly slower. It sounds like you might be interested in what Okasaki calls a "random access list", but between Seq and IntMap, you'd best analyze your specific algorithm and benchmark.
