[Haskell-cafe] Importance of identity element in finger trees?

Ross Paterson ross at soi.city.ac.uk
Sat Jul 18 06:04:10 EDT 2009


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.


More information about the Haskell-Cafe mailing list