Haskell § data-structures

Data structures

Haskell’s principal data structures live in three places: the language itself (lists, tuples, Maybe, Either), the Data.* modules of base (which include some optimised collection types), and external libraries (notably containers for Map, Set, Sequence; vector for arrays; text for strings). The conventional foundation is the singly-linked list — the [a] type — which has linguistic privileges (the : constructor, list-comprehension syntax, the implicit list-monad instance) and is the lingua franca of much of the standard library. For non-trivial work, programmers reach for Data.Map, Data.Set, Data.Sequence, or Data.Vector for their respective specialisations.

This page covers the principal containers, the choice among them, the iterator equivalents (the Foldable and Traversable classes), and the conventions for using each.

Lists

The list type [a] is a singly-linked list:

data [a] = [] | a : [a]    -- conceptually

The : is the cons constructor; [] is the empty list. Lists admit a literal syntax [1, 2, 3] and range syntax [1..10]:

xs :: [Int]
xs = []
ys = [1, 2, 3, 4, 5]
zs = [1..10]               -- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ws = [1, 3..10]            -- [1, 3, 5, 7, 9]
infinite = [1..]

Standard list operations:

Operation	Effect	Complexity
`length xs`	Number of elements	O(n)
`null xs`	Whether the list is empty	O(1)
`head xs`, `tail xs`	First / rest	O(1) (partial)
`last xs`, `init xs`	Last / all-but-last	O(n)
`xs ++ ys`	Concatenation	O(length xs)
`x : xs`	Prepend (cons)	O(1)
`xs !! i`	Index (partial)	O(i)
`take n xs`, `drop n xs`	First / last n	O(n)
`reverse xs`	Reverse	O(n)
`map f xs`	Apply f to each	O(n)
`filter p xs`	Keep where p	O(n)
`foldr f z xs`, `foldl f z xs`	Reduce	O(n)

Several operations are partial — they fail on certain inputs:

head / tail / init / last of [] produce a runtime error.
xs !! i for i < 0 or i >= length xs produces a runtime error.

The conventional defences:

Use Data.Maybe.listToMaybe for safe head: listToMaybe :: [a] -> Maybe a.
Use Data.List.uncons (since base 4.8): uncons :: [a] -> Maybe (a, [a]).
Pattern-match explicitly: case xs of { [] -> ...; (x:_) -> ... }.

List comprehensions

squares = [x * x | x <- [1..10]]
evens = [x | x <- [1..20], even x]
pairs = [(x, y) | x <- [1..3], y <- [1..3], x /= y]

The form is syntactic sugar for map, filter, and concatMap. Treated in Loops.

When `[a]` is the wrong choice

Lists are not always the right choice:

Random access is O(n); use Vector or Array for O(1) access.
Length is O(n); use Vector, Sequence, or Map if length is queried frequently.
Concatenation is O(left length); for many concatenations, use Sequence (O(log n) concat).
Storage overhead is high — each cell is two words (the value and the next pointer), which can be 16+ bytes per element for small types.

For substantial collections, consider Vector; for ordered keyed data, Map; for set membership, Set. The conventional advice is to start with [] for simplicity and switch when measurement justifies it.

Tuples

A tuple is an anonymous fixed-arity record:

pair :: (Int, String)
pair = (42, "hello")

triple :: (Int, String, Bool)
triple = (1, "ok", True)

unit :: ()
unit = ()

The fst and snd functions extract the first and second components of a pair:

fst :: (a, b) -> a
snd :: (a, b) -> b

For tuples larger than 2 (or for cases where named access is preferable), use a record. Tuples have no field names; pattern matching is the conventional access mechanism:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

`Maybe` and `Either`

Two essential types:

data Maybe a = Nothing | Just a
data Either a b = Left a | Right b

Maybe represents “an a or nothing”:

findUser :: Int -> [User] -> Maybe User
findUser id = listToMaybe . filter ((== id) . userId)

Either represents “an a or a b”; conventionally, Left is the error case and Right is the success case:

parse :: String -> Either String Int
parse s = case reads s of
    [(n, "")] -> Right n
    _         -> Left ("could not parse: " ++ s)

Both types admit substantial library support. Common functions:

import Data.Maybe

fromMaybe :: a -> Maybe a -> a
maybe :: b -> (a -> b) -> Maybe a -> b
catMaybes :: [Maybe a] -> [a]                      -- discard Nothings
mapMaybe :: (a -> Maybe b) -> [a] -> [b]            -- map and discard Nothings

import Data.Either

either :: (a -> c) -> (b -> c) -> Either a b -> c
fromLeft :: a -> Either a b -> a
fromRight :: b -> Either a b -> b
lefts :: [Either a b] -> [a]
rights :: [Either a b] -> [b]
partitionEithers :: [Either a b] -> ([a], [b])

The full treatment of Maybe and Either as effects (through the Functor/Applicative/Monad instances) is in Functors and applicatives and Monads.

`Data.Map.Strict` and `Data.Map.Lazy`

The containers package provides a balanced-tree-based map:

import qualified Data.Map.Strict as Map
import Data.Map.Strict (Map)

m :: Map String Int
m = Map.fromList [("alice", 30), ("bob", 28), ("carol", 35)]

age :: Maybe Int
age = Map.lookup "alice" m       -- Just 30

m' :: Map String Int
m' = Map.insert "dave" 32 m

m'' = Map.delete "bob" m

The principal operations:

Operation	Effect	Complexity
`Map.empty`	Empty map	O(1)
`Map.singleton k v`	One-element map	O(1)
`Map.fromList xs`	From a list of pairs	O(n log n)
`Map.lookup k m`	`Maybe v`	O(log n)
`Map.member k m`	Whether k is present	O(log n)
`Map.insert k v m`	Insert or overwrite	O(log n)
`Map.delete k m`	Remove	O(log n)
`Map.size m`	Number of entries	O(1)
`Map.keys m`, `Map.elems m`	Lists of keys / values	O(n)
`Map.toList m`	List of pairs	O(n)
`Map.union m1 m2`	Union	O(n + m)
`Map.intersectionWith f`	Intersection with combiner	O(n + m)
`Map.foldrWithKey f z m`	Fold with key access	O(n)
`Map.map f m`, `Map.filter p m`	Map / filter	O(n)
`Map.alter f k m`	Modify or insert/delete	O(log n)

Data.Map.Strict evaluates values strictly when inserted; Data.Map.Lazy (the default Data.Map) evaluates lazily. The strict variant is the conventional choice for accumulator-style use.

The keys must be Ord instances; the comparison function is the natural ordering. For unordered access, see Data.HashMap.

`Data.Set`

A balanced-tree-based set:

import qualified Data.Set as Set
import Data.Set (Set)

s :: Set Int
s = Set.fromList [1, 2, 3, 4, 5]

has3 :: Bool
has3 = Set.member 3 s

s' :: Set Int
s' = Set.insert 6 s

s'' = Set.delete 1 s

union :: Set Int
union = Set.union (Set.fromList [1, 2, 3]) (Set.fromList [3, 4, 5])

The principal operations are analogous to Map’s. The keys must be Ord.

For unordered membership, Data.HashSet from unordered-containers provides O(log n) average-case operations through hashing.

`Data.Sequence`

A finger-tree-based sequence with O(log n) concat and indexed access:

import qualified Data.Sequence as Seq
import Data.Sequence (Seq, ViewL(..), ViewR(..), (|>), (<|))

s :: Seq Int
s = Seq.fromList [1, 2, 3, 4, 5]

s' = 0 <| s                  -- prepend; O(log n) amortised
s'' = s |> 6                 -- append; O(log n) amortised

case Seq.viewl s of
    EmptyL -> "empty"
    x :< rest -> "head: " ++ show x

i :: Maybe Int
i = Seq.lookup 2 s           -- Just 3

The principal operations:

Operation	Effect	Complexity
`Seq.fromList xs`	From a list	O(n)
`Seq.length s`	Length	O(1)
`Seq.lookup i s`	Index	O(log n)
`Seq.update i x s`	Update at index	O(log n)
`s1 >< s2`	Concatenate	O(log(min n m))
`x <\| s`	Prepend	O(1) amortised
`s \|> x`	Append	O(1) amortised
`Seq.viewl s`	View from left	O(1)
`Seq.viewr s`	View from right	O(1)

The Seq is the conventional choice when both ends and indexed access are needed. For only one-end-fast and high-throughput, Data.IntMap.Strict keyed on indices is also an option.

`Data.Vector`

A packed array, from the vector package:

import qualified Data.Vector as V
import Data.Vector (Vector)

v :: Vector Int
v = V.fromList [1, 2, 3, 4, 5]

x :: Int
x = v V.! 2                  -- O(1) indexing

v' :: Vector Int
v' = V.map (* 2) v

The vector package provides:

Data.Vector — boxed arrays (each element is a heap-allocated value).
Data.Vector.Unboxed — unboxed arrays for primitive types (Int, Double, Bool); avoid the heap allocation per element.
Data.Vector.Storable — for types stored as raw bytes (interop with C).
Data.Vector.Mutable — mutable variants for in-place updates within ST or IO.

The vector package is the conventional choice for substantial array work. For numeric workloads, Data.Vector.Unboxed is the right choice; for arbitrary types, Data.Vector (boxed) is appropriate.

Operation	Effect	Complexity
`V.fromList xs`	From list	O(n)
`V.length v`	Length	O(1)
`v V.! i`	Index (partial)	O(1)
`v V.!? i`	Safe index	O(1)
`V.head v`, `V.last v`	First / last	O(1)
`V.map f v`, `V.filter p v`	Standard ops	O(n)
`V.toList v`	To list	O(n)
`V.replicate n x`	Constant	O(n)
`V.zip v1 v2`	Pair	O(n)
`V.foldr f z v`, `V.foldl' f z v`	Reduce	O(n)

Foldable and Traversable

Many higher-order operations work on any foldable container:

import Data.Foldable

length :: Foldable t => t a -> Int
sum :: (Foldable t, Num a) => t a -> a
elem :: (Foldable t, Eq a) => a -> t a -> Bool
toList :: Foldable t => t a -> [a]
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

The instances exist for [], Maybe, Either e, Map k, Set, Tree, Seq, Vector, and many user-defined types. The mechanism admits writing one polymorphic version of each operation that works for every foldable container.

Traversable extends Foldable with effectful traversal:

import Data.Traversable

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)

The full treatment is in Functors and applicatives and Monads.

The choice between containers

A typical decision tree:

Need	Container
Default sequence	`[a]`
Lookup by key	`Map k v`
Lookup by key, fast (no Ord)	`HashMap k v` (from `unordered-containers`)
Set membership	`Set a`
Set membership, fast	`HashSet a`
Random access on a sequence	`Vector a`
Random access on numeric data	`Vector.Unboxed a`
Both ends fast, with indexing	`Seq a`
Stack	`[a]` (use `:` and `tail`)
Queue	`Seq a` (or `[a]` with two-list amortised technique)
Snapshot-shared	Any of the above (immutable by default)
Mutable	`MutableArray`, `MVar`, `IORef` (in IO/ST)

The default for “I need a collection” is [a] for simplicity; switch when measurement justifies a more specialised container.

Iterator-like traversal

Haskell has no separate iterator concept; Foldable and the standard list operations admit traversal:

-- Sum a foldable:
total :: Foldable t => t Int -> Int
total = sum

-- Filter a foldable to a list:
filtered :: Foldable t => (a -> Bool) -> t a -> [a]
filtered p = filter p . toList

-- Effectful traversal:
mapM_ print someContainer

The patterns admit working uniformly across container types.

Common patterns

Counting occurrences

import qualified Data.Map.Strict as Map

countOccurrences :: Ord a => [a] -> Map.Map a Int
countOccurrences = foldr (\x -> Map.insertWith (+) x 1) Map.empty

The Map.insertWith admits “insert with a combiner if the key is already present” — the conventional pattern for accumulators.

Grouping

import Data.List (groupBy, sortBy)
import Data.Function (on)

groupByFirst :: [(Int, String)] -> [(Int, [String])]
groupByFirst = map (\group -> (fst (head group), map snd group))
             . groupBy ((==) `on` fst)
             . sortBy (compare `on` fst)

The groupBy requires sorted input (it groups adjacent equal elements). For map-based grouping:

import qualified Data.Map.Strict as Map

groupByKey :: Ord k => [(k, v)] -> Map.Map k [v]
groupByKey = foldr (\(k, v) -> Map.insertWith (++) k [v]) Map.empty

Building a lookup

import qualified Data.Map.Strict as Map

idToUser :: [User] -> Map.Map Int User
idToUser = Map.fromList . map (\u -> (userId u, u))

Partition

import Data.List (partition)

(positives, negatives) = partition (> 0) [-1, 2, -3, 4, 5, -6]
-- positives = [2, 4, 5], negatives = [-1, -3, -6]

Removing duplicates

import Data.List (nub)

unique :: Eq a => [a] -> [a]
unique = nub                      -- O(n²); slow for large lists

import qualified Data.Set as Set

uniqueSet :: Ord a => [a] -> [a]
uniqueSet = Set.toList . Set.fromList    -- O(n log n)

The nub from Data.List is the standard form but is O(n²); for substantial lists, the Set-based form is preferable.

A note on persistence

All Haskell data structures are persistent: an operation produces a new structure without modifying the old one. The mechanism admits structural sharing — the new structure shares much of its internal nodes with the old, so the cost of an “update” is logarithmic rather than linear:

let m1 = Map.fromList [(1, "a"), (2, "b"), (3, "c")]
    m2 = Map.insert 4 "d" m1
-- m1 and m2 share most of their internal structure
-- the cost of insert is O(log n), not O(n)

The persistence model admits safe sharing across threads (no synchronisation needed; immutable values are race-free), undo/redo through retaining old versions, and reasoning about programs without considering aliasing. The cost is a per-operation logarithmic factor compared to in-place mutation; for most workloads this is negligible.

For workloads where mutation matters (substantial in-place numeric work, large arrays), the ST and IO monads admit mutable state through MutableArray, IORef, and similar; the mutable structures convert back to immutable at boundaries.