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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
