Common Algorithms and Data Structures

Sorting, compared

Pearls already built two genuinely different sorting algorithms — Quicksort (partition around a pivot) and Mergesort (split, sort halves, merge). A third, simpler than either, rounds out the comparison:

insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []
  where
    insert x []     = [x]
    insert x (y:ys)
      | x <= y      = x : y : ys
      | otherwise   = y : insert x ys

ghci> insertionSort [5,3,8,1]
[1,3,5,8]

insert slides one element into its correct position in an already-sorted list; foldr (Chapter 3) builds the whole sorted list one insertion at a time, right to left. It’s the most direct possible transcription of “keep a sorted pile, slide each new card into place” — genuinely how most people sort a hand of playing cards.

Algorithm	Best	Average	Worst	Stable?
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	yes
Quicksort (Pearls)	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	yes*
Mergesort (Pearls)	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	yes

* the list-based Quicksort from Pearls happens to preserve relative order of equal elements; a mutating, in-place Quicksort generally does not.

Mergesort’s worst case never degrades, because its split point is always the midpoint by position (Pearls) — Insertion Sort’s worst case is an already-reverse-sorted list, where every single insertion has to walk all the way to the far end.

Searching: why the data structure matters as much as the algorithm

Linear search needs no ceremony — elem already is linear search, walking the list until it finds a match or runs out, $O(n)$ either way. Binary search is the famous $O(\log n)$ improvement — but only if it’s built on the right foundation.

import Data.Array

binarySearch :: Ord a => a -> Array Int a -> Maybe Int
binarySearch target arr = go lo hi
  where
    (lo, hi) = bounds arr
    go l h
      | l > h     = Nothing
      | otherwise =
          let mid    = (l + h) `div` 2
              midVal = arr ! mid
          in case compare target midVal of
               EQ -> Just mid
               LT -> go l (mid - 1)
               GT -> go (mid + 1) h

Trees: building a binary search tree from scratch

A binary search tree (BST) keeps values ordered so that everything in a node’s left subtree is smaller, and everything in its right subtree is larger — the same ordering invariant that makes binary search on an array work, just expressed as a shape instead of a sorted sequence.

data BST a = Leaf | Node (BST a) a (BST a)

insert :: Ord a => a -> BST a -> BST a
insert x Leaf = Node Leaf x Leaf
insert x t@(Node l y r)
  | x < y     = Node (insert x l) y r
  | x > y     = Node l y (insert x r)
  | otherwise = t   -- already present

member :: Ord a => a -> BST a -> Bool
member _ Leaf = False
member x (Node l y r)
  | x < y     = member x l
  | x > y     = member x r
  | otherwise = True

toList :: BST a -> [a]
toList Leaf         = []
toList (Node l x r) = toList l ++ [x] ++ toList r

toList’s in-order traversal — left subtree, then the node, then right subtree — always produces a sorted list, for free, as a direct consequence of the insertion invariant; it’s a nice self-check that insert is behaving correctly. insert and member both run in $O(\log n)$ on average, following exactly the halving pattern the figure shows — but only on average.

Dictionaries and sets: Data.Map and Data.Set

Hand-rolling a BST is the right way to understand an ordered dictionary; Data.Map, from the containers package, is the right way to actually use one — a genuinely balanced, guaranteed-$O(\log n)$ tree, battle-tested, and already in nearly every Haskell project’s dependency tree.

import qualified Data.Map as Map

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

ghci> wordCounts ["the","cat","sat","on","the","mat"]
fromList [("cat",1),("mat",1),("on",1),("sat",1),("the",2)]

ghci> Map.lookup "the" (wordCounts ["the","cat","the"])
Just 2

Map.insertWith (+) w 1 reads as “insert w with value 1, or if w is already a key, combine the old and new values with (+)” — the classic word-frequency counter, in one line. Data.Set, from the same package, is the same balanced-tree idea with no attached values at all — conceptually close to a Map k (), used whenever membership alone (not an associated value) is what matters:

import qualified Data.Set as Set

ghci> Set.member 3 (Set.fromList [1,2,3,4])
True
ghci> Set.fromList [1,2,3] `Set.union` Set.fromList [3,4,5]
fromList [1,2,3,4,5]

The throughline across this whole chapter is the same one Pearls opened with: a naive, obviously-correct version first (insertionSort, a hand-rolled BST), then the real, production-hardened version once the underlying idea is genuinely understood (Data.Map, self-balancing trees, array-backed binary search) — clarity earning its way to performance, never skipping straight to the second half.