CODEWITHSUNDEEP
haskellcollections
aa22
aa22

Reputation: 39

Data.IntMap vs Data.Sequence in Haskell (Haskell Collections)

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?

Upvotes: 3

Views: 242

Answers (1)

dfeuer
dfeuer

Reputation: 48611

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.

Upvotes: 3

Related Questions