generic finger-tree structure (http://staff.city.ac.uk/~ross/papers/FingerTree.html)
#11Generalize to semigroups?
The requirement that the tree annotations form a monoid seems to introduce extra overhead for in some applications. Could that be improved by relaxing from Monoid to Semigroup and taking on a Maybe (or similar) when necessary? For example, I believe that for a priority queue, a very natural annotation would be simply Data.Semigroup.Min k. This should, I believe avoid an extra indirection at each node. We could preserve fast access to the minimal key and its value by stashing them aside in the root node.