Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 57 ยท Modules, packages and tooling

Essential Libraries: containers, text, bytestring, vector

Meet the Haskell libraries almost every project uses: Data.Map and Data.Set, Data.Sequence, Text, ByteString and Vector, and learn how to pick the right one.

The Prelude gives you linked lists, and linked lists are wonderful for teaching and for streaming through data once. They are poor at everything else: finding an element takes time proportional to the length, ++ copies, and indexing walks from the front. Real programs reach for a handful of libraries that fix each of those weaknesses.

This lesson introduces the five you will meet most: containers (maps, sets, sequences), text, bytestring and vector. You add each to build-depends as explained in Cabal, Stack and Packages. The real code is read-only because GHC is not available on this site; a JavaScript stand-in at the end models how an immutable map behaves.

Pick by the job

Map Look things up by key.
Set Membership and no duplicates.
Seq Fast at both ends.
Vector Fast indexing by position.
1 / 2

Qualified imports

These libraries export names such as map, filter, lookup and null that clash with the Prelude. The convention is to import the module qualified with a short alias, and only unqualify the type name:

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

Now Map is the type and Map.lookup is the function. Every library below follows this pattern. (Qualified imports are covered in detail in Modules and Imports.)

Data.Map: key-value lookup

Data.Map from the containers package is a balanced binary search tree. Keys must have an Ord instance, and lookup, insert and delete take O(log n) time. Maps are immutable: Map.insert returns a new map and shares most of the old structure.

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

type Inventory = Map String Int

stock :: Inventory
stock = Map.fromList [("apple", 5), ("pear", 2)]

main :: IO ()
main = do
  print (Map.lookup "apple" stock)            -- Just 5
  print (Map.lookup "kiwi" stock)             -- Nothing
  print (Map.findWithDefault 0 "kiwi" stock)  -- 0
  let stock' = Map.insertWith (+) "apple" 3 stock
  print (Map.toList stock')                   -- [("apple",8),("pear",2)]

Notes:

  • lookup returns a Maybe, so a missing key is a value you must handle (see Maybe and Either).
  • insertWith f key new combines the new value with an existing one using f new old. It is the standard way to count things.
  • Map.toList returns pairs in ascending key order, always.
  • Other everyday functions: member, delete, adjust, alter, unionWith, foldrWithKey, Map.map, Map.filter.

Use Data.Map.Strict rather than Data.Map.Lazy unless you need lazy values. The strict module evaluates values as they are inserted, which avoids the thunk build-up described in Strictness, Bang Patterns and seq.

A word-frequency counter shows why folds and maps go together:

HASKELL
wordCounts :: [String] -> Map String Int
wordCounts = foldr (\w -> Map.insertWith (+) w 1) Map.empty

If you have non-comparable keys or need hashing, the unordered-containers package offers HashMap, with the same style of API.

Data.Set: membership

Data.Set is a map without values. It keeps its elements sorted and unique, and member, insert and delete are O(log n).

HASKELL
import qualified Data.Set as Set

main :: IO ()
main = do
  let s = Set.fromList [3, 1, 2, 3, 1 :: Int]
  print s                          -- fromList [1,2,3]
  print (Set.member 2 s)           -- True
  print (Set.toList (Set.union s (Set.fromList [9, 8])))  -- [1,2,3,8,9]

Set.fromList removes duplicates, which makes Set.size . Set.fromList a quick way to count distinct items. Union, intersection and difference are built in.

Data.Sequence: fast at both ends

A list is cheap to add to at the front only. Data.Sequence (also in containers) supports adding and removing at either end in O(1) amortised time, and indexing or splitting in O(log n). It is a good queue.

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

main :: IO ()
main = do
  let q = Seq.fromList [1, 2, 3 :: Int] |> 4
  print (Seq.length q)             -- 4
  print (Seq.index q 2)            -- 3
  case viewl q of
    x :< rest -> print (x, Seq.length rest)   -- (1,3)
    EmptyL    -> putStrLn "empty"

Patterns Empty, x :<| rest and rest :|> x are also available and read nicely in a recursive function. Choose Seq when you need a FIFO queue, a deque, or frequent splitting and concatenation.

Text: Unicode strings that are not lists

String is [Char]: each character costs a list cell plus a boxed Char, which is many times larger than the text itself. The text package stores Unicode text in a compact array and is the type most modern libraries expect.

HASKELL
# LANGUAGE OverloadedStrings #

import Data.Text (Text)
import qualified Data.Text as T
import qualified Data.Text.IO as TIO

greeting :: Text
greeting = "  Hello, Haskell  "

main :: IO ()
main = do
  TIO.putStrLn (T.toUpper (T.strip greeting))   -- HELLO, HASKELL
  print (T.splitOn "," "a,b,c")                 -- ["a","b","c"]
  print (T.length greeting)                     -- 18
  print (T.unpack "hi")                         -- "hi"

OverloadedStrings lets the literal "..." be a Text (see GHC Extensions Worth Knowing). Convert with T.pack and T.unpack when you must meet a String. The introduction to text handling is in Strings, Chars and Text. Always use Data.Text.IO for reading and printing Text, not putStrLn from the Prelude, which expects String.

ByteString: bytes, not characters

bytestring represents raw bytes: file contents, network packets, hashes, binary formats. It has no encoding. Use Data.ByteString for binary data and Data.ByteString.Char8 only when the bytes are really ASCII. For text in a known encoding, decode to Text with Data.Text.Encoding (decodeUtf8).

HASKELL
import qualified Data.ByteString as BS

main :: IO ()
main = do
  let bytes = BS.pack [72, 105, 33]
  print bytes                      -- "Hi!"
  print (BS.length bytes)          -- 3

Strict ByteString holds all the data in memory; the .Lazy variants read in chunks and are useful for streaming big files.

Vector: indexing by position

vector provides arrays with O(1) indexing and good performance for numeric work.

HASKELL
import qualified Data.Vector as V

main :: IO ()
main = do
  let v = V.fromList [10, 20, 30, 40 :: Int]
  print (v V.! 2)                  -- 30
  print (V.sum (V.map (* 2) v))    -- 200
  print (V.generate 5 (^ 2))       -- [0,1,4,9,16]

Because vectors are immutable, an update such as v V.// [(1, 99)] copies the whole vector in O(n). For many updates use the mutable interface in Data.Vector.Mutable inside the ST monad (see Mutable State: IORef, MVar and ST), or reconsider whether a Map or Seq fits better. Variants such as Data.Vector.Unboxed store plain numbers without boxing for extra speed.

How to choose

Need Pick
Look up by key Map (or HashMap)
Is this value in the collection? Set
Queue or deque Seq
Random access by index, numeric arrays Vector
Process once, front to back plain list
Human-readable text Text
Binary data ByteString

Lists remain the right tool for small data and for lazy pipelines, where each element is produced and consumed once. Switch only when the access pattern demands it.

A stand-in: an immutable map

JavaScript has no persistent map in its standard library, so this stand-in copies a Map on every update. Real Haskell shares structure instead of copying, but the visible behaviour is the same: the old map is unchanged.

JS Immutable map and word counts (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

toList sorts the entries because a Haskell Map always lists its keys in order, while a JavaScript Map remembers insertion order.

The same idea applies to sets. A Set is a collection of distinct, sorted items:

JS Set operations (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why are these libraries usually imported qualified?

    Map.lookup and Prelude lookup would be ambiguous. A short qualified alias avoids the clash.
  2. 2. What does Map.insertWith (+) "a" 1 m do when "a" is already in m?

    insertWith combines the new and old values with the given function, which makes it ideal for counting.
  3. 3. Which type is the best fit for a FIFO queue?

    Seq supports adding and removing at both ends in O(1) amortised time.
  4. 4. Why prefer Text over String for large amounts of text?

    A String is a list of boxed characters, which uses far more memory and is slower to process.
  5. 5. What does v V.// [(1, 99)] cost on an immutable Vector of n elements?

    Immutable vectors are copied on update. For many updates use a mutable vector in ST or another structure.

Summary

  • Import containers, text, bytestring and vector modules qualified, with short aliases.
  • Map gives O(log n) lookup by key; Set gives membership; both keep keys sorted and need Ord.
  • Seq is a good queue; Vector gives O(1) indexing but O(n) updates.
  • Text replaces String for real text; ByteString holds raw bytes.
  • Prefer Data.Map.Strict to avoid thunk build-up in values.
  • Lists remain best for small data and one-pass lazy pipelines.

Next: Testing: HUnit, Hspec and QuickCheck.