General purpose data structure implementations, including sets, maps, sequences, and more. For fixed size arrays, see the "Arrays" page.
Note: The maps above have 'lazy' and 'strict' implementations, in most cases you'll want the strict version, see the notes in the
unordered-containers sections below for more info.
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.
Specialized data structures
- Heterogeneous lists: HList
- Tries: bytestring-trie
- Graphs: fgl, algebraic-graphs
- Difference lists: dlist
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.
stm-containers is a great library for situations where you need to access a map/set from several threads but avoid doing global locking.
Efficient general-purpose implementations of various immutable ordered container types. This package includes:
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 (
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).
A list-like type supporting O(1) append, useful for efficient logging and pretty printing.
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