I was talking about advent of code with a colleague, we had a small internal leaderboard at work last year. And so I told him “you should look at betaveros, he’s one of the best at advent of code, he even designed his own language named Noulith to solve it, it is super impressive”.
Betaveros has a full post about it on his blog, that I did read twice in the past, I also did read some bits of the Rust implementation last year to understand more about it. The whole blog is pure gold of impressive knowledge.
And since I redid my website a little bit on the design side, I saw my old post in 2011 about implementing Peter Norvig’s did you mean in Java, OCaml, Python and also Elixir. So I wondered if I can rewrite the did you mean algorithm with nice features Noulith.
Noulith describes itself as a language for quick and dirty scripts with an unreasonable amount of syntax sugar. That sounds totally appropriate for this exercise.
The algorithm will stay unchanged, we build a frequency table from a corpus, then generate every word one edit away. If none are known we try with two edits away, finally among the known candidates we choose the most frequent one.
Click to directly see the final version
First version
The first version stays very close to the Python implementation:
freq := frequencies(search_all(lower(read_file("big.txt")), "[a-z]+"));
alphabet := "abcdefghijklmnopqrstuvwxyz";
edits1 := \w -> (
splits := for (i <- 0 to len(w)) yield [w[:i], w[i:]];
set((for ((a,b) <- splits; if b) yield a$b[1:]) ++
(for ((a,b) <- splits; if len(b)>1) yield a$b[1]$b[0]$b[2:]) ++
(for ((a,b) <- splits; c <- alphabet; if b) yield a$c$b[1:]) ++
(for ((a,b) <- splits; c <- alphabet) yield a$c$b))
);
known := \xs -> set(xs filter (\x -> x in freq));
edits2 := \w -> set(for (x <- edits1(w); y <- edits1(x); if y in freq) yield y);
correct := \w -> (
candidates := known({w}) or known(edits1(w)) or edits2(w) or {w};
max(candidates, \a,b -> freq[a] <=> freq[b])
);
argv each (\w -> print(w$" -> Did you mean "$correct(w)$" ?"));
Although it is already compact it does not use much of what makes Noulith an interesting language.
% time noulith v1.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith v1.noul speling korrectud 0.43s user 0.01s system 98% cpu 0.450 total
Using Noulith features a little more
There are several features in Noulith that we can use for this algorithm.
For example, frequencies(...) directly builds the frequency dictionary, while search_all(...) extracts the words from the corpus.
Then we can replace the explicit construction of every split with prefixes(w) zip reverse(suffixes(w)), because those two sequences give us exactly the left and right parts of the word at every possible position.
The zip function can also receive a function, so instead of repeating for ((a,b) <- splits) four times we can process each pair directly with zip(..., \a,b -> ...).
The delete operation is simply a $ b[1:], while the transpose can be written using slices as a $ b[1:2] $ b[:1] $ b[2:]. That means we can remove the guards such as if b and if len(b) > 1, because invalid cases only generate the original word and the final set(...) removes duplicates anyway.
Replacement and insertion are also almost identical, since their only difference is whether we append b[1:] or b, so the cartesian product operator ** lets us generate both at once with "abcdefghijklmnopqrstuvwxyz" ** [b[1:], b].
Sets and dictionaries are very close concepts in Noulith, and && computes their intersection, meaning that freq && edits(w) directly replaces the known(...) function while keeping the frequencies from freq. The second level of edits becomes e flat_map edits, which removes the need for a separate edits2 function altogether.
Lastly "abcdefghijklmnopqrstuvwxyz" can be written "a" to "z", which is nice.
With those features the same algorithm becomes:
freq := frequencies(search_all(lower(read_file("big.txt")), "[a-z]+"));
edits := \w -> set(flatten(zip(
prefixes(w), reverse(suffixes(w)),
\a,b -> [a$b[1:],a$b[1:2]$b[:1]$b[2:]] ++
(("a" to "z") ** [b[1:],b] map (\(c,t) -> a$c$t))
)));
correct := \w -> (
e := edits(w);
candidates := (freq&&{w}) or (freq&&e) or (freq&&set(e flat_map edits)) or {w};
max(candidates,\a,b -> freq[a] <=> freq[b])
);
argv each (\w -> print(w$" -> Did you mean "$correct(w)$" ?"));
This version is 11 non-empty lines, and more importantly it no longer has explicit for comprehensions, known, edits2. Indices to construct the split and guards inside the edit generation are gone also.
% time noulith v2.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith v2.noul speling korrectud 0.43s user 0.02s system 98% cpu 0.458 total
Golfing it a little more
Let’s shorten the names and formatting while still keeping something I would potentially be willing to read:
freq:=frequencies(search_all(lower(read_file("big.txt")),"[a-z]+"));
edit:=\w->set(flatten(zip(prefixes(w),reverse(suffixes(w)),\a,b->[a$b[1:],a$b[1:2]$b[:1]$b[2:]]++(("a"to"z")**[b[1:],b] map(\(c,t)->a$c$t)))));
corr:=\w->(x:=edit(w);c:=(freq&&{w})or(freq&&x)or(freq&&set(x flat_map edit))or{w}; max(c,\a,b->freq[a]<=>freq[b]));
argv each(\w->print(w$" -> Did you mean "$corr(w)$" ?"));
We are now at 4 lines of code (388 characters).
% time noulith golf.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith golf.noul speling korrectud 0.44s user 0.02s system 99% cpu 0.460 total
Can we go even smaller?
A little bit 😜
Noulith’s reverse function application with . lets us turn the corpus loading into a pipeline, so frequencies(search_all(lower(read_file("big.txt")),"[a-z]+")) becomes "big.txt".read_file.lower.search_all("[a-z]+").frequencies.
The cartesian product operator ** is also n-ary, which means replacement and insertion can be generated with [a]**("a"to"z")**[b[1:],b] map join(""), avoiding another lambda.
freq:="big.txt".read_file.lower.search_all("[a-z]+").frequencies;
edit:=\w->zip(w.prefixes,w.suffixes.reverse,\a,b->[a$b[1:],a$b[1:2]$b[:1]$b[2:]]++([a]**("a"to"z")**[b[1:],b] map join(""))).flatten.set;
corr:=\w->(x:=edit(w);c:=(freq&&{w})or(freq&&x)or(freq&&set(x flat_map edit))or{w};max(c,\a,b->freq[a]<=>freq[b]));
argv each(\w->print(w$" -> Did you mean "$corr(w)$" ?"));
With those two tricks we are still at 4 lines but with 10 less characters.
% time noulith golf.v2.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith golf.v2.noul speling korrectud 0.28s user 0.02s system 97% cpu 0.305 total
One last Noulith trick
There is one last Noulith feature I can think of to shorten the selection of the best candidate. The <=> operator is a three-way comparison operator, and on transforms it into a comparator based on another function, so <=> on (\x -> freq[x]) compares two words using their frequencies rather than the words themselves.
Noulith also expose indexing as the !! operator and the partial application rules allow freq(!!) to mean the function that indexes freq, so that means it is equivalent to \x -> freq[x]. So we can reduce the comparator to <=> on freq(!!).
Final version
This gives us the final 3 lines (346 characters) version:
freq:="big.txt".read_file.lower.search_all("[a-z]+").frequencies;
edit:=\w->zip(w.prefixes,w.suffixes.reverse,\a,b->[a$b[1:],a$b[1:2]$b[:1]$b[2:]]++([a]**("a"to"z")**[b[1:],b] map join(""))).flatten.set;
argv each(\w->(x:=edit(w);print(w$" -> Did you mean "$max((freq&&{w})or(freq&&x)or(freq&&set(x flat_map edit))or{w},<=> on freq(!!))$" ?")));
% time noulith final.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith final.noul speling korrectud 0.28s user 0.02s system 98% cpu 0.307 total
At this point we could still put everything on a single physical line because Noulith wouldn’t care.
Anyway, I spent already too much time on this…
Kudos to betaveros for this very interesting and beautiful little language.
Maybe he can even do better, so if you’re reading this by any chance do not hesitate.
Until next time!