A word can be a string, and the input text a list of those strings. Use names that avoid clashing with the Standard Prelude machine-word type
Word:type TextWord = String
type Text = [TextWord]Thus . These are type synonyms, so ordinary string and list operations remain available without wrapping or unwrapping constructors. They describe input that has already been tokenized; punctuation and word boundaries do not need a separate treatment here.
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 wAfter 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 provesfor 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 input words and distinct normalized words, it performs 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.Compare frequencies in decreasing order and use lexicographic order on words to break ties. Implement merge sort explicitly, so no imported sorting routine is needed:
-- Entry, TextWord and Frequency are as in part (b).
before :: Entry -> Entry -> Bool
before (w, p) (v, q) = p > q || (p == q && w <= v)
sort :: [Entry] -> [Entry]
sort [] = []
sort [x] = [x]
sort xs = merge (sort left) (sort right)
where
(left, right) = splitAt (length xs `div` 2) xs
merge :: [Entry] -> [Entry] -> [Entry]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
| before x y = x : merge xs ya
| otherwise = y : merge xa ysThe merge algorithm step always emits the smaller key under the ordering . The unchosen heads cannot precede that emitted entry because each input is already sorted. It preserves all entries, and each call removes one head, so it terminates with exactly the sorted union of the inputs. Mathematical induction over the recursive splits establishes correctness of merge sort.
For entries, splitting and merging cost per level, and there are levels:The base cases take constant time. This counts word comparisons as primitive operations, as in the question. If the maximum compared word length is , the character-operation bound becomes , in addition to frequency comparison costs.
For the supplied input,
sort . count yields[("baa",2),("sir",2),("yes",2),("any",1),("bags",1),("black",1),
("full",1),("have",1),("sheep",1),("three",1),("wool",1),("you",1)]In particular, the secondary ordering places
sir before yes, even though yes appears earlier in the original text. The requirement concerns sort; the simpler association list implementation of count has its own cost. Articles by others on the same topic
There are currently no matching articles.