Essential Data Structures

24.1 Data.Map and Data.Set (containers)

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

phoneBook :: Map String String
phoneBook = Map.fromList [("ana", "555-1234"), ("bo", "555-9876")]

Map.lookup "ana" phoneBook                 -- Just "555-1234"
Map.findWithDefault "?" "cy" phoneBook     -- "?"
Map.insert "cy" "555-0000" phoneBook
Map.delete "bo" phoneBook
Map.member "ana" phoneBook                 -- True
Map.size phoneBook                         -- 2
Map.toList phoneBook                       -- sorted by key
Map.adjust (++ " (mobile)") "ana" phoneBook
Map.alter (fmap (++ "!")) "ana" phoneBook
Map.insertWith (+) "x" 1 (Map.fromList [("x", 5)])   -- fromList [("x",6)]
Map.unionWith (+) m1 m2
Map.foldrWithKey (\k v acc -> k ++ "=" ++ v ++ ";" ++ acc) "" phoneBook
Map.filter (isPrefixOf "555") phoneBook

wordCount :: String -> Map String Int
wordCount = Map.fromListWith (+) . map (\w -> (w, 1)) . words

s = Set.fromList [3, 1, 4, 1, 5]           -- fromList [1,3,4,5]
Set.member 4 s, Set.insert 9 s, Set.union s s, Set.intersection s s, Set.toList s

-- Also in containers: Data.IntMap, Data.IntSet, Data.Sequence (finger trees: O(1) both ends),
-- Data.Tree, Data.Gra
…

24.2 Text

{-# LANGUAGE OverloadedStrings #-}          -- string literals become Text/ByteString
import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import Data.Text (Text)

greeting :: Text
greeting = "Hello, World"

T.length greeting, T.toUpper greeting, T.words "a b c", T.splitOn "," "a,b,c"
T.strip "  hi  ", T.replace "World" "Haskell" greeting, T.isPrefixOf "He" greeting
T.pack "from String", T.unpack greeting, T.intercalate ", " ["a", "b"]
main = TIO.readFile "input.txt" >>= TIO.putStrLn . T.toUpper   -- strict, Unicode-aware

import qualified Data.Text.Encoding as TE
bytes = TE.encodeUtf8 greeting               -- Text → ByteString
-- TE.decodeUtf8' for safe decoding (returns Either)

24.3 ByteString

import qualified Data.ByteString as BS             -- strict bytes
import qualified Data.ByteString.Lazy as BL        -- lazy chunks (streams of strict chunks)
import qualified Data.ByteString.Char8 as BC       -- ASCII/Latin-1 convenience
copyFile' :: FilePath -> FilePath -> IO ()
copyFile' a b = BS.readFile a >>= BS.writeFile b
countLines :: FilePath -> IO Int
countLines f = length . BC.lines <$> BC.readFile f
-- Builder (Data.ByteString.Builder) for efficient output construction

24.4 Vector and Arrays

import qualified Data.Vector as V                  -- boxed, immutable, O(1) indexing
import qualified Data.Vector.Unboxed as VU         -- unboxed primitives (much faster for numbers)
v = V.fromList [1 .. 10 :: Int]
V.sum v, v V.! 3, V.map (* 2) v, V.filter even v, V.slice 2 3 v, V.length v
VU.sum (VU.enumFromN (1 :: Int) 1000000)           -- fused loop, no intermediate structure
-- Also: Data.Array (Haskell 98 arrays), massiv (multi-dimensional, parallel), hmatrix (linear algebra)

24.5 Choosing Data Structures

Data.HashMap.Strict (unordered-containers) Data.Set, Data.HashSet Data.Vector / Data.Vector.Unboxed

Data.Text (and Data.Text.Lazy for streaming) Small sequences, stack-like use