Word frequency with the standard library

A complete program that counts word occurrences in a sentence: it splits text on whitespace, folds case, tallies with a hash map, and reports the most frequent word's count. Every piece comes from the standard library, so this is also a tour of how four std: modules compose.

use std.str.*;
use std.map.*;
use std.list.*;
use std.sort.*;

// A string literal reaches a `Str` through a data segment: `Str` is a GC byte array, and
// `new Str[n] data<D>(0)` fills one from a segment. The length must match the segment's
// byte count exactly.
data Sentence = "the cat sat on the mat and the cat left";

export func check as "check";
func check() -> i32 {
  let text: &Str = new Str[39] data<Sentence>(0);

  // `split_whitespace` discards empty pieces, unlike `split`, so runs of spaces and any
  // leading or trailing space produce no blank words.
  let words: &StrList = text.split_whitespace();

  // Keys are the words' hashes rather than the words themselves, because `IntMap` is the
  // cheaper structure and this program never needs to recover the word from the key. Use
  // `StrMap` when you do -- it compares keys by content, so a rebuilt equal string finds
  // its entry.
  let counts: &IntMap = int_map();
  for i in 0..#words {
    // `.at(i)` hands back a non-null `&Str`: `StrList`'s elements are nullable only
    // because a runtime-length GC array must be default-initializable.
    let word: &Str = words.at(i).to_lower();
    // One probe, not a get-then-put pair.
    counts.increment(word.hash(), 1);
  }

  // `values()` returns an `IntList`; `to_array` gives the plain `&I32Values` that `sort`
  // takes. They are the same array type across both modules, which is exactly why
  // `std.array` declares it once for everyone.
  let tallies: &I32Values = counts.values().to_array();
  sort(tallies);

  let distinct: i32 = counts.len();
  let most_common: i32 = tallies[#tallies - 1];

  // 10 words, 7 distinct ("the" x3, "cat" x2), so the top tally is 3.
  return #words - 10 + distinct - 7 + most_common - 3;
}

What each module contributes

Module	Used for
std.str	Str, split_whitespace, to_lower, hash
std.map	IntMap, increment, values
std.list	IntList.to_array
std.sort	sort over &I32Values

std.array is never imported by name here, yet I32Values resolves. That is because std.map and std.list both import it, and the module loader merges each file into the compilation unit exactly once — so the type is present, and it is the same type in every module that mentions it.

Why the hash is the key

counts.increment(word.hash(), 1) tallies by hash, which collapses two different words that happen to collide. For a word-frequency counter over real text that is a bug waiting to happen, and the fix is StrMap, which stores the key itself and compares by content:

use std.str.*;
use std.map.*;

data Words = "red green red blue red";
data Red = "red";

export func check as "check";
func check() -> i32 {
  let text: &Str = new Str[22] data<Words>(0);
  let words: &StrList = text.split_whitespace();

  // A `StrMap` value is `?any`, so a count is boxed into an `i31` -- the standard way to
  // put an integer where a reference is expected.
  let counts: &StrMap = str_map();
  for i in 0..#words {
    let word: &Str = words.at(i);
    let (existing, found): (?any, i32) = counts.get(word);
    var n: i32 = 0;
    // The two-result `get` is what distinguishes "absent" from "present and zero"; a
    // sentinel could not, since every count is a legitimate value.
    if (found != 0) {
      if (existing is &i31) { n = existing as i32.u; }
    }
    counts.put(word, (n + 1) as &i31);
  }

  let red: &Str = new Str[3] data<Red>(0);
  let (value, ok): (?any, i32) = counts.get(red);
  var red_count: i32 = 0;
  if (value is &i31) { red_count = value as i32.u; }

  // 5 words, 3 distinct, "red" appears 3 times.
  return #words - 5 + counts.len() - 3 + red_count - 3 + ok - 1;
}

What this costs

Only what it uses. Four modules are imported with .*, which makes roughly 150 functions visible; the emitted module contains 29:

$ reedc build word_frequency.reed -o out.wat
$ grep -c '(func \$' out.wat
29

Those 29 are check plus exactly the library functions it can reach: sort, sort_by, and the sift_down helper sort_by calls — but not sort_stable, binary_search, lower_bound, or anything else in std.sort. Reachability is transitive in both directions: a helper reached only through a reached function is kept, and one reachable only from an unreached function is dropped.

Related

• Standard library — every module and what it provides
• Modules — how import and the flat namespace work
• GC narrowing — the is tests this example uses to unbox an i31
• Multi-file programs — the same import machinery over your own files