This afternoon I took a stroll around Harvard with some friends. I can recommend without reservation Harvard Square on a sunny summer Sunday afternoon and Herrell’s Mudpie flavor.
I spent much of the weekend building a generic monoid-annotated self-balancing binary tree with bidirectional links and stable leaves. I’m not sure why monoid-annotated trees are so little-known, as they are super-useful. I learned about them here, though that author incorrectly refers to them as Finger Trees.
Anyway, they’re pretty cool. Using the monoid for summation over the integers, and an enhanced AA balancing procedure I was able to build a list with O(log(N)) performance for lookup, insertion, deletion, and search.
Beautiful.
EDIT: Turns out WordPress really doesn’t like certain Unicode characters…