= Solution
Normalize each word once by applying `toLower` to its characters. Maintain an <association list> whose keys are distinct normalized words and whose values are their frequencies:
``
import Data.Char (toLower)
type TextWord = String
type Text = [TextWord]
type Frequency = Integer
type Entry = (TextWord, Frequency)
count :: Text -> [Entry]
count = foldl addWord [] . map (map toLower)
where
-- Increment the unique matching key, or append a new key with count one.
addWord :: [Entry] -> TextWord -> [Entry]
addWord [] w = [(w, 1)]
addWord ((v, n):rest) w
| w == v = (v, n + 1) : rest
| otherwise = (v, n) : addWord rest w
``
After any input prefix, each normalized word seen so far occurs exactly once as a key, with its number of occurrences as value. This <loop invariant> holds initially for the empty <association list>. A step either increments the unique existing entry or introduces exactly one new entry, so <mathematical induction> proves
$$
\boxed{\operatorname{lookup}\ w\ (\operatorname{count}\ \mathrm{input})=\operatorname{Just}(\text{number of normalized occurrences of }w)}
$$
for every word that occurs. In particular, `Baa` and `baa` contribute to the same key `baa`; the three frequency-two keys in the source example are `baa`, `yes` and `sir`.
The <association list> preserves first-occurrence order, although the specification allows any order here. For $t$ input words and $d$ distinct normalized words, it performs $O(td)$ key comparisons in the worst case. Character normalization costs the total input character count, and a <string> comparison can inspect multiple characters. Characterwise `toLower` supplies the intended <case-insensitive comparison> convention for the example; full Unicode case folding can require a different normalization policy.
Back to article page
