On Sat, Jul 18, 2009 at 03:57:12AM -0400, Daniel Peebles wrote:
I was looking at finger trees and the tricks for getting priority queues out of them seemed a little hackish, with a distinguished infinity element or maxBound. But it seems (although I have not yet tried it) like in many cases the monoid's identity element wouldn't be necessary (a bit like the difference between fold* and fold*1). Could a finger tree be applied to an arbitrary semigroup? Or is the identity more fundamental than it looks?
Two answers: 1) It can be applied to an arbitrary semigroup, because you can always turn that into a monoid by adding an identity element. 2) It suffices to have an associative operation with a left identity (exercise 7 in the paper). But an identity is still needed, as the measure of the empty tree. You could special case that, but it would be equivalent to 1) above.