Introduction

Haskell’s standard ordered map type, Data.Map, is implemented with balanced trees because that design fits persistent immutable data, ordered traversal, and predictable O(log n) behavior. Traditional hash tables are still available in the Haskell ecosystem, but they solve a different problem and require different tradeoffs.

Map And HashMap Serve Different Goals

A common source of confusion is assuming there is one canonical map abstraction. In Haskell, there are at least two major families:

• 'Data.Map, which is ordered and based on balanced trees'
• 'Data.HashMap.Strict from unordered-containers, which is hash-based'

So the better question is not "why did Haskell reject hash tables" but "why is the standard ordered Map tree-based".

Immutability Favors Structural Sharing

Haskell data structures are usually persistent, meaning updates return a new structure while preserving the old one. Balanced binary trees fit this extremely well because an insertion or deletion only needs to rebuild the nodes on one search path and can share the rest of the structure.

1import qualified Data.Map as M
2
3m1 = M.fromList [(2, "b"), (1, "a")]
4m2 = M.insert 3 "c" m1
5
6main = do
7  print m1
8  print m2

m1 remains available after m2 is created. Tree-based persistence makes that efficient because most of the old structure is reused.

Ordering Is A First-Class Feature

Data.Map requires an Ord instance for keys, not a Hashable instance. That means the map maintains keys in sorted order and can support operations that hash tables do not provide naturally:

• ordered traversal
• range queries
• 'lookupLT, lookupGT, and similar neighbor queries'
• efficient splitting and merging by key order

These are not side benefits. They are central to why a balanced tree is the right structure for an ordered map.

Predictable Complexity Matters

Balanced trees offer O(log n) lookup, insertion, and deletion in both typical and worst-case usage. Hash tables often have excellent average behavior, but their complexity depends on hash quality, resizing behavior, and collision handling.

In a purely functional setting, predictable asymptotics and structural reasoning are especially attractive because the data structure semantics are exposed directly in library design.

Why Not Make Hash Tables The Default

Hash tables are great when you need fast average-case lookup and ordering does not matter. But they come with tradeoffs:

• you need a good hash function
• iteration order is not key order
• persistence is less natural than path-copying in trees
• some operations depend on bucket layout rather than key structure

That does not make them bad. It just makes them a different tool.

Example Of Ordered Behavior

The sorted nature of Map is visible immediately.

1import qualified Data.Map as M
2
3main = do
4  let m = M.fromList [(3, "c"), (1, "a"), (2, "b")]
5  print (M.toList m)

This prints the entries in ascending key order, regardless of insertion order. That property is valuable in many functional programs where deterministic traversal is desirable.

When HashMap Is Better

If you do not need ordering and you do have a suitable Hashable instance, a hash-based map may be the better choice.

1import qualified Data.HashMap.Strict as HM
2
3main = do
4  let m = HM.fromList [("cat", 1), ("dog", 2)]
5  print (HM.lookup "dog" m)

This is the right tool for many lookup-heavy workloads where ordering and range operations do not matter.

Common Pitfalls

The most common mistake is treating Map as if it were supposed to optimize the exact same workload as a mutable hash table in an imperative language. Its design goals are broader and more persistent-data-structure friendly.

Another mistake is ignoring the existence of HashMap. Haskell does support hash-based maps; they are simply not the same abstraction as Data.Map.

A third issue is undervaluing order. Once you need deterministic sorted traversal or key-neighbor operations, balanced trees become much more compelling than traditional hash tables.

Summary

• 'Data.Map is tree-based because it is an ordered, persistent map.'
• Balanced trees support structural sharing naturally in immutable code.
• They also provide sorted traversal and range-style operations.
• Hash tables still exist in Haskell through libraries such as unordered-containers.
• Choose Map for ordered semantics and HashMap for hash-based average-case lookup.