Haskell list indexing with !! is slow for a lookup table: should I use Vector, Array, Map or Seq?

A Haskell list is a singly linked list, so xs !! i walks i cells, length walks all of them, and lookup scans pairs until it finds the key. Looking up each of 100,000 positions once costs about 100,000² / 2 = 5 billion steps in total. Each cell is also a separate heap object pointing to a separately boxed Double, which is hard on the cache.

Lists are good at what linked lists are good at: prepending in constant time, pattern matching on head and tail, and being produced and consumed lazily as a stream. Use them for iteration, not for random access.

For a fixed table indexed by integer, use Data.Vector.Unboxed from the vector package. It is a contiguous block of raw doubles with constant-time indexing: table = V.fromList values and table V.! i, or table V.!? i to get a Maybe instead of an exception when the index is out of range. For 100,000 doubles the payload is 800,000 bytes, against several times that for a list.

The boxed Data.Vector holds pointers to lazy values and works for any element type; the unboxed variant works for primitive types such as Int, Double, Word8 and tuples of them. The package supplies the familiar map, foldl', zipWith and sum for both.

For the name-to-value pairs, use Data.Map.Strict from containers. It is a balanced binary tree with O(log n) lookup, insert and delete; 100,000 entries need about 17 comparisons per lookup, since log2 of 100,000 is roughly 16.6. Build it with Map.fromList pairs and query with Map.lookup name m, which returns a Maybe.

For Int keys Data.IntMap.Strict is faster still, and Data.Set is the same idea for membership tests. Prefer the .Strict modules when the values are counters or totals, for example Map.insertWith (+) key 1 m, so that they do not build up unevaluated additions.

The remaining two have narrower roles. Data.Array is the older array type from the array package; its distinguishing feature is flexible indices, including tuples, so Array (Int, Int) Double is a convenient two-dimensional grid. Data.Sequence is a finger tree with cheap insertion and removal at both ends and O(log n) indexing, splitting and concatenation, which makes it a good queue or deque.

One warning for all immutable arrays and vectors: changing a single element produces a full copy, so an update inside a loop is O(n) each time. If you need many in-place writes, build the result in one pass with functions like V.generate, or use the mutable vectors in the ST monad and freeze the result.