Write this accumuator in a functional style

[Paul Rubin]

Chris Angelico <rosuav at gmail.com> writes:
> Maybe I'm completely on the wrong track here, but the last time I
> implemented a self-balancing tree, it usually involved a fair amount
> of mutation.

AVL trees are fairly simple to implement without mutation.  Red-black
trees are traditionally implemented with mutation, inserting by making
nodes mis-colored, then going and re-coloring them.  But they can be
done mutation-free as well.  Here's an amazing Haskell implementation
where the tree invariants are encoded in the datatype:

https://gist.github.com/rampion/2659812

Reddit discussion of above:  https://redd.it/ti5il

More recent versions of GHC make the type signatures even nicer, since
you can put numbers directly into types without that nested type encoding.