Based on a suggestion by Alistair Turnbull, this latest Haskell exercise involves creating a randomly balanced tree codata type (at least, I think it’s a codata type). (Edit: nope, it’s a coalgebra. Or at least, I think it is)

Updates to the tree are merged with a stream of random numbers, which are used to reorder nodes within the tree.

The rule is that the random number attached to the parent node must always be greater than the random number attached to either of its child nodes.

This has the effect of shuffling the tree so that it remains balanced even in degenerate cases (e.g. adding an already sorted sequence of values to the tree, which without balancing would result in a linked list with lookups in linear-time rather than logarithmic time).

I am impressed with the simplicity and effectiveness of this technique. Improvements to my implementation of it here are warmly solicited.