Introduction

In Haskell, the default list type [a] is a linked list with O(n) lookup by index or value. For fast element lookup, Haskell provides several immutable data structures: Data.Map (balanced BST with O(log n) key lookup), Data.HashMap (hash-based with O(1) average lookup), Data.Set (O(log n) membership testing), Data.IntMap (specialized O(log n) for Int keys), and Data.Vector (O(1) indexed access). Choosing the right structure depends on whether you need key-value lookup, membership testing, or indexed access.

List Lookup (O(n) — Baseline)

1-- List lookup is O(n) — linear scan
2-- By index:
3xs = [10, 20, 30, 40, 50]
4element = xs !! 2  -- 30, but O(n) because lists are linked
5
6-- By value (membership):
7found = 30 `elem` xs  -- True, O(n) scan
8
9-- Association list lookup:
10pairs = [("alice", 1), ("bob", 2), ("charlie", 3)]
11result = lookup "bob" pairs  -- Just 2, O(n) scan

Lists work for small collections but become a bottleneck for anything larger than a few hundred elements. Every lookup traverses the list from the beginning.

Data.Map (O(log n) Key-Value Lookup)

1import qualified Data.Map.Strict as Map
2
3-- Create a map from a list of pairs
4students :: Map.Map String Int
5students = Map.fromList [("alice", 95), ("bob", 82), ("charlie", 91)]
6
7-- Lookup: O(log n)
8score = Map.lookup "bob" students       -- Just 82
9missing = Map.lookup "dave" students    -- Nothing
10
11-- Insert: O(log n)
12updated = Map.insert "dave" 88 students
13
14-- Delete: O(log n)
15removed = Map.delete "bob" students
16
17-- Update: O(log n)
18adjusted = Map.adjust (+5) "alice" students  -- alice -> 100
19
20-- Fold over all entries
21total = Map.foldl' (+) 0 students  -- 268
22
23-- Convert back to list
24pairs = Map.toAscList students
25-- [("alice",95),("bob",82),("charlie",91)]

Data.Map.Strict is a balanced binary search tree (size-balanced tree). Keys must be Ord. It maintains sorted order and provides O(log n) for lookup, insert, and delete. Use Map.Strict over Map.Lazy to avoid space leaks from unevaluated thunks.

Data.HashMap (O(1) Average Lookup)

1import qualified Data.HashMap.Strict as HM
2
3-- Create a hash map
4users :: HM.HashMap String Int
5users = HM.fromList [("alice", 1), ("bob", 2), ("charlie", 3)]
6
7-- Lookup: O(1) average
8result = HM.lookup "alice" users  -- Just 1
9
10-- Insert: O(1) average
11updated = HM.insert "dave" 4 users
12
13-- Delete: O(1) average
14removed = HM.delete "bob" users
15
16-- Size
17count = HM.size users  -- 3

Data.HashMap from the unordered-containers package uses hash array mapped tries (HAMT). It requires Hashable and Eq on keys. For String and Text keys, it is faster than Data.Map for large collections.

Data.Set (O(log n) Membership)

1import qualified Data.Set as Set
2
3-- Create a set
4primes :: Set.Set Int
5primes = Set.fromList [2, 3, 5, 7, 11, 13, 17, 19, 23]
6
7-- Membership test: O(log n)
8isPrime = Set.member 7 primes   -- True
9notPrime = Set.member 4 primes  -- False
10
11-- Insert and delete: O(log n)
12extended = Set.insert 29 primes
13reduced = Set.delete 2 primes
14
15-- Set operations: O(n + m)
16evens = Set.fromList [2, 4, 6, 8, 10]
17common = Set.intersection primes evens  -- fromList [2]

Use Data.Set when you only need to check whether an element exists, without associated values. It is more memory-efficient than a Map with dummy values.

Data.IntMap (O(log n) for Int Keys)

1import qualified Data.IntMap.Strict as IntMap
2
3-- Specialized map for Int keys — faster than Map Int
4scores :: IntMap.IntMap String
5scores = IntMap.fromList [(1, "alice"), (2, "bob"), (3, "charlie")]
6
7-- Lookup: O(min(n, W)) where W = word size (typically 64)
8result = IntMap.lookup 2 scores  -- Just "bob"
9
10-- Insert
11updated = IntMap.insert 4 "dave" scores
12
13-- Efficient union
14other = IntMap.fromList [(5, "eve"), (6, "frank")]
15combined = IntMap.union scores other

Data.IntMap uses a Patricia trie internally and is significantly faster than Map Int for integer keys. The complexity is O(min(n, W)) where W is the bit width (64 on modern systems), which is effectively O(1) for practical purposes.

Data.Vector (O(1) Indexed Access)

1import qualified Data.Vector as V
2
3-- Create a vector (immutable array)
4grades :: V.Vector Int
5grades = V.fromList [85, 92, 78, 95, 88]
6
7-- Index access: O(1)
8third = grades V.! 2  -- 78
9
10-- Safe index access
11safe = grades V.!? 10  -- Nothing
12
13-- Map and fold: O(n)
14doubled = V.map (* 2) grades
15total = V.foldl' (+) 0 grades  -- 438
16
17-- Slice: O(1)
18middle = V.slice 1 3 grades  -- [92, 78, 95]

Data.Vector provides O(1) indexed access (like arrays in imperative languages). Use it when you need fast random access by position rather than key-value lookup.

Comparison Table

* Effectively O(1) due to bounded key width.

Common Pitfalls

• Using lists for lookup-heavy code: Lists are linked — every lookup is O(n). Switching from lookup key pairs to Map.lookup key map reduces lookup from O(n) to O(log n). For large datasets, this is the single most impactful performance improvement.
• Using Data.Map.Lazy instead of Data.Map.Strict: The lazy variant delays evaluation of values, accumulating thunks that consume memory. Use Data.Map.Strict (and IntMap.Strict, HashMap.Strict) unless you specifically need lazy semantics.
• Forgetting to use foldl' (strict fold): foldl (without the prime) builds up a chain of unevaluated thunks, causing stack overflow on large collections. Always use foldl' or foldl' from the strict module for numeric accumulations.
• Choosing Map when IntMap or HashMap would be faster: Map requires Ord and uses tree comparisons. If keys are Int, IntMap is 2-5x faster. If keys are String or Text and order does not matter, HashMap is faster for large collections.
• Using Vector for frequent insertions: Data.Vector is immutable — inserting an element requires copying the entire array (O(n)). Use Data.Sequence for O(log n) insertion at arbitrary positions, or use mutable vectors (Data.Vector.Mutable) inside ST or IO.

Summary

• Use Data.Map for ordered key-value lookup with Ord keys (O(log n))
• Use Data.HashMap for unordered key-value lookup with Hashable keys (O(1) average)
• Use Data.Set for membership testing without associated values
• Use Data.IntMap for Int keys — significantly faster than Map Int
• Use Data.Vector for O(1) indexed random access (array-like behavior)
• Always use the Strict variants of Map, IntMap, and HashMap to avoid space leaks