General purpose data structure implementations, including sets, maps, sequences, and more. For fixed size arrays, see the "Arrays" page.

Recommendations

The containers and unordered-containers packages are the de facto data structure libraries for Haskell. Both of these libraries contain tuned implementations of persistent data structures.

Sequences: Sequence
Sets: Set, HashSet, IntSet
Maps: Map, HashMap, IntMap

Note: The maps above have 'lazy' and 'strict' implementations, in most cases you'll want the strict version, see the notes in the containers and unordered-containers sections below for more info.

Performance:

The containers and unordered-containers packages both have the Big-O complexity of each operation documented. Benchmark results comparing different implementations can be be found at the links below.

Sequences benchmarks: https://github.com/haskell-perf/sequences
Set benchmarks: https://github.com/haskell-perf/sets
Dictionary benchmarks: https://github.com/haskell-perf/dictionaries

Specialized data structures

Data science and machine learning

If you're doing data science (numerical methods, machine learning, etc.) then see datahaskell.org's "current environment" page for more information on data structures and algorithms suited for this problem space.

Concurrency

stm-containers is a great library for situations where you need to access a map/set from several threads but avoid doing global locking.

edit description
or press Ctrl+Enter to savemarkdown supported
#
unordered-containers (Hackage)
unordered
move item up move item down edit item info delete item
Summary edit summary

Efficient hashing-based container types including HashSet and HashMap.

Strict or Lazy hashmap? If:

  • you will eventually need all the values stored, or
  • the stored values don't represent large virtual data structures to be lazily computed

then you should use the Data.HashMap.Strict.

Summary quit editing summary
#
containers (Hackage)
ordered
move item up move item down edit item info delete item
Summary edit summary

Efficient general-purpose implementations of various immutable ordered container types. This package includes: Maps, Sets, Trees, Graphs, and Seqs.

Strict or Lazy map? If:

  • you will eventually need all the values stored, or
  • the stored values don't represent large virtual data structures to be lazily computed

then you should use the strict version of each of the container type (Data.IntMap.Strict, Data.Map.Strict).

Tutorial: https://haskell-containers.readthedocs.io.

Summary quit editing summary
#
HList (Hackage)
list
move item up move item down edit item info delete item
Summary edit summary

Creation and manipulation of heterogenous lists (HLists) whose length and element types are known at compile-time.

Summary quit editing summary
#
bytestring-trie (Hackage)
trie
move item up move item down edit item info delete item
Summary edit summary

An efficient finite map from (byte)strings to values.

If all you need to do is associate strings to values you should use either Map from containers or HashMap from unordered-containers. You should only use this if you need the extra capabilities that a trie can provide (structure sharing for highly redundant keys, submap of all keys with a given prefix, extracting minimum and maximum keys, etc).

Summary quit editing summary
#
dlist (Hackage)
list
move item up move item down edit item info delete item
Summary edit summary

A list-like type supporting O(1) append, useful for efficient logging and pretty printing.

Example

Using DList as the state type when printing a tree with the Writer monad from dlist docs:

import Control.Monad.Writer
import Data.DList

data Tree a = Leaf a | Branch (Tree a) (Tree a)

flatten_writer :: Tree x -> DList x
flatten_writer = snd . runWriter . flatten
    where
      flatten (Leaf x)     = tell (singleton x)
      flatten (Branch x y) = flatten x >> flatten y
Summary quit editing summary
Summary edit summary

Alga (this package) is a library for algebraic construction and manipulation of graphs in Haskell. See the README for more information.

Summary quit editing summary
#
fgl (Hackage)
graph
move item up move item down edit item info delete item
Summary edit summary

An inductive representation of manipulating graph data structures.

TODO: Better description.

Summary quit editing summary