Write this accumuator in a functional style
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:
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.