Data.Map and Data.Set

Lists are great for sequences, but slow for lookups. The containers package provides efficient immutable maps (dictionaries) and sets, implemented as balanced trees with O(log n) operations.

Data.Map

import qualified Data.Map.Strict as Map

main :: IO ()
main = do
  let ages = Map.fromList [("Ada", 36), ("Alan", 41), ("Grace", 85)]
  print (Map.lookup "Ada" ages)
  print (Map.lookup "Linus" ages)
  print (Map.findWithDefault 0 "Linus" ages)
  print (Map.member "Alan" ages, Map.size ages)
  let ages2 = Map.insert "Linus" 54 (Map.delete "Alan" ages)
  print ages2
  print (Map.adjust (+ 1) "Ada" ages2 Map.! "Ada")
  print (Map.keys ages2, Map.elems ages2)
  print (Map.filter (> 50) ages2)
  print (Map.toList (Map.map (* 2) ages2))

Just 36
Nothing
0
(True,3)
fromList [("Ada",36),("Grace",85),("Linus",54)]
37
(["Ada","Grace","Linus"],[36,85,54])
fromList [("Grace",85),("Linus",54)]
[("Ada",72),("Grace",170),("Linus",108)]

• Data.Map.Strict evaluates values as they're inserted — prefer it over lazy Data.Map unless you need lazy values.
• Maps are immutable: insert returns a new map (sharing most of its structure with the old one).
• Map.! crashes on a missing key; lookup and findWithDefault are safe.
• Keys must be Ord, and toList/keys return them in sorted order.

Counting and grouping

import qualified Data.Map.Strict as Map
import Data.Char (toLower, isAlpha)

wordFreq :: String -> Map.Map String Int
wordFreq = Map.fromListWith (+) . map (\w -> (w, 1)) . words . map normalize
  where
    normalize c = if isAlpha c then toLower c else ' '

main :: IO ()
main = do
  let text = "The cat and the hat. The cat sat!"
  print (Map.toList (wordFreq text))
  let byLength = Map.fromListWith (++) [(length w, [w]) | w <- words "a bb cc ddd e"]
  print byLength
  print (Map.insertWith (+) "cat" 10 (wordFreq text) Map.! "cat")
  print (Map.foldrWithKey (\k v acc -> k ++ "=" ++ show v ++ " " ++ acc) "" (Map.fromList [("x", 1), ("y", 2)]))

[("and",1),("cat",2),("hat",1),("sat",1),("the",3)]
fromList [(1,["e","a"]),(2,["cc","bb"]),(3,["ddd"])]
12
"x=1 y=2 "

fromListWith f combines values for duplicate keys with f — the idiomatic way to count and group. It calls f new old, which is why the grouped words come out in reverse order (["e","a"]).

Data.Set

import qualified Data.Set as Set

main :: IO ()
main = do
  let a = Set.fromList [3, 1, 4, 1, 5, 9, 2, 6]
      b = Set.fromList [2, 7, 1, 8]
  print a
  print (Set.member 4 a, Set.size a)
  print (Set.union a b)
  print (Set.intersection a b)
  print (Set.difference a b)
  print (Set.toList (Set.map (`mod` 3) a))

fromList [1,2,3,4,5,6,9]
(True,7)
fromList [1,2,3,4,5,6,7,8,9]
fromList [1,2]
fromList [3,4,5,6,9]
[0,1,2]

Other containers

• Data.IntMap / Data.IntSet — faster versions for Int keys.
• Data.Sequence — a finite sequence with fast access at both ends and O(log n) indexing.
• Data.HashMap (from unordered-containers) — hash maps, for keys that are Hashable rather than Ord.
• Data.Array and the vector package — arrays with O(1) indexing.

Practice

Given a list of (city, temperature) readings, build a Map from each city to its highest temperature.

import qualified Data.Map.Strict as Map

main :: IO ()
main = do
  let readings = [("Oslo", 12), ("Lima", 19), ("Oslo", 15), ("Lima", 17), ("Pune", 31)]
  print (Map.fromListWith max readings)

fromList [("Lima",19),("Oslo",15),("Pune",31)]