Haskell containers

Haskell’s standard package of persistent containers: Data.Sequence (finger trees), Data.Map and Data.Set (weight-balanced trees), Data.IntMap (Patricia trees), plus trees and graphs.

What it is: Purely functional data structures (finger trees)
Type: Open source
Made by: Haskell core libraries maintainers
License: BSD-3-Clause
Facts checked: 9 October 2026

What it is

The containers package ships with GHC and is the default place Haskell programs get maps, sets and sequences. All of its types are immutable, and every stated cost, worst-case or amortized, still holds when versions are shared. Data.Map and Data.Set are size-balanced binary trees (trees of bounded balance, after Adams 1993 and Nievergelt and Reingold 1973), so lookup, insert and delete take O(log n) and an update copies one path. Data.IntMap and Data.IntSet use big-endian Patricia trees after Okasaki and Gill, which are especially fast at union and intersection.

Data.Sequence is the best-known production finger tree: Hinze and Paterson’s 2-3 finger trees annotated with sizes. It gives O(1) access at both ends, O(log n) concatenation, splitting and indexing, and lazy internals so that fmap, zipWith, replicate and similar functions build results incrementally. Unlike a list, a Seq is always finite and strict in its length, and it makes a “rather mediocre” stack: if you only push and pop at one end, a list is faster.

The package grew out of modules first written for other libraries: Data.Map carries a 2002 copyright by Daan Leijen and Data.Sequence a 2005 one by Ross Paterson. It became a separate package when GHC 6.8.1 split the old base library in November 2007. It is actively maintained: 0.8 came out in March 2025 and 0.8.1 on 4 October 2026, and more than 6,000 Hackage packages depend on it directly.

Why teams pick it

Ships with GHC and is used by thousands of packages, so it is the common currency for maps, sets and sequences
Every bound holds under persistent use, so keeping and reusing old versions never breaks performance
Data.Sequence covers deques, indexing, splitting and concatenation with one type
Strict and lazy variants of maps (Data.Map.Strict, Data.Map.Lazy) to control thunk build-up

Watch out for

Seq is slower than a list for stack-like use and slower than an array for indexing, even when the big-O is the same or better
No hash maps: unordered hashing lives in the separate unordered-containers package
A Seq must be finite, and its size must not exceed maxBound :: Int; going over is not detected

How it fits with other technologies

What Haskell containers uses

Haskell containersis a core library shipped withHaskellProgramming languages

A finger-tree sequence and a weight-balanced map (containers 0.7, GHC 9.10) · haskell

import qualified Data.Map.Strict as Map
import Data.Sequence ((<|), (|>), (><))
import qualified Data.Sequence as Seq

main :: IO ()
main = do
  -- a finger tree: O(1) at both ends, O(log n) split, join and index
  let s1 = Seq.fromList [1 .. 100000 :: Int]
      s2 = 0 <| (s1 |> 100001) -- s1 is unchanged
      (left, right) = Seq.splitAt 50000 s2
  print (Seq.length s1, Seq.length s2) -- (100000,100002)
  print (Seq.index right 0, Seq.lookup 3 left) -- (50000,Just 3)
  print (Seq.length (right >< left)) -- 100002

  -- a weight-balanced tree: insert copies one path, old map stays valid
  let prices = Map.fromList [("tea", 3), ("cake", 5)] :: Map.Map String Int
      prices' = Map.insertWith (+) "tea" 1 prices
  print (Map.lookup "tea" prices, Map.lookup "tea" prices') -- (Just 3,Just 4)
  print (Map.toAscList prices') -- [("cake",5),("tea",4)]

See it in a real stack

No architecture uses Haskell containers yet. Drop it into the playground and wire it up yourself.Open playground →

Where it came from2002–2026

Data.Map traces back to Daan Leijen’s 2002 implementation of Stephen Adams’s weight-balanced trees, a design from a 1993 functional pearl that keeps a size in every node. Data.IntMap followed Okasaki and Gill’s big-endian Patricia trees for integer keys, which merge quickly.

In 2005 Ross Paterson added Data.Sequence, based on the 2-3 finger trees that Paterson and Ralf Hinze published in the Journal of Functional Programming in 2006. Their paper notes that the sequence implementation of its section 4.2 is included in GHC and other Haskell implementations. When GHC 6.8.1 split the monolithic base library in November 2007, these modules became containers 0.1, a new library “split off from base”. GHC still bundles it as a dependency of the compiler itself: GHC 9.10.3 ships containers 0.7.

Why it’s built this way

Weight-balanced trees for Map and Set: Storing each subtree’s size in its node keeps the tree balanced with simple rules, and the docs give precise bounds for set operations such as union and intersection.
Finger trees for Seq: One structure with cheap ends, logarithmic split and concatenation, and size annotations for indexing covers queues, deques and random access lists.
Bounds that hold under sharing: Haskell values are persistent by default, so the package states every cost, worst-case or amortized, as valid even when structures are shared.
A separate package from base: Splitting base in GHC 6.8.1 let containers be versioned and released on its own while still shipping with the compiler.

Timeline

2002
Daan Leijen writes Data.Map (copyright date in the module)
2005
Ross Paterson adds Data.Sequence
2007
GHC 6.8.1 (3 November) splits containers 0.1 off from base
2012
containers 0.5.0.0
2023
containers 0.7
2025
containers 0.8 (March)
2026
containers 0.8.1 (October)

Sources9 · facts checked 9 October 2026

Improve this page on GitHub