Oct 26, 2026, 1:18 PMThe great thing about functional pearl papers is that they are short enough to be printed out so you can highlight and write notes on the pages and have it by your side while implementing.
- Oct 26, 2026, 1:18 PM
Replies
- Oct 28, 2026, 4:06 PM
something I realized last night: since diets are a sort of meta-tree that can delete nodes during insert (when the new interval overlaps or is adjacent to two existing intervals) and add nodes during deletion (when the interval to be deleted is a subset of an existing interval), that means that both operations need to incorporate the red-black tree insertion and deletion algorithms.
- Oct 29, 2026, 1:26 AM
okay I seem to have a successful fusion of diets and red-black trees. let's call them "balanced diets".
- Oct 29, 2026, 1:29 PM
I started comparing balanced diets to guile's intsets as the results are as expected. if the set stored in a diet is actually dense (a lot of adjacent ints) and thus the tree is shallower than the intset's prefix tree then it's faster to query the diet. otherwise the intset's 32-way branching wins.
it's also much faster to add contiguous ranges of numbers to a diet because it was built for this and you don't have to insert one number at a time.