Comment by chas | Hacker News Reader

Comment by chas | Hacker News Reader

I'm happy to see finger trees got mentioned. Finger trees[0] are extremely useful and general data structure that can be used to implement persistent sequences, priority queues, search trees and priority search queues. (Haskell's Data.Sequence[1] uses specialized 2-3 finger trees internally) They can form the basis of all sorts of interesting custom structures by supplying the appropriate monoid[3], but this does make them harder to approach if you are not familiar with the abstractions.

[3] A monoid is any structure that has members that can combine associatively. In addition, it must have an element that can combine with any other element and result in the other element. Some examples: (strings, string concatenation, the empty string); (integers, addition, 0); (natural numbers, max, 0); (booleans, and, True); (functions, composition, the identity function). The functional pearl[2] that describes the design of Haskell's diagrams library[4] goes into much more detail if you are interested in their application to programming.

[0] http://apfelmus.nfshost.com/articles/monoid-fingertree.html

[1] http://hackage.haskell.org/package/containers-0.5.4.0/docs/D...

[2] http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf

[4] http://projects.haskell.org/diagrams/

"In addition, it must have an element that can combine with any other element and result in the other element."

Aka, an identity element.

Monoids that have inverses (that is, every element has another element that, when combined, produces the identity element) are "groups". Of the examples you gave:

"Strings over composition" does not form a group - there's nothing you can concatenate with a non-empty string to get an empty string.

"Integers over addition" does form a group. The inverse of x is -x.

"Natural numbers over max" is not a group. Once you get above 0 you cannot get back to it just by applying max.

"Booleans over and" is not a group. Once you have false you can't get back to true.

"Functions over composition" is not a group. Many functions have inverses, but some do not. If you restrict the set to "functions with inverses" then you do have a group.

Exactly. I was trying to avoid any mathematical jargon while describing monoids because they are such general and pervasive structures in programming. Further, being able to construct useful new monoids is crucial for making full use of a finger tree and I didn't want to have someone find an interesting structure unapproachable because they had to walk through an abstract algebra jargon storm in order to understand it. I realize I referenced associativity without describing it, so I didn't quite achieve my goal, but hopefully the examples got the idea across to someone who might otherwise have dismissed it due to the perception that it was too academic and unapproachable.

As an aside, trying to remove the jargon from a definition like this is surprisingly hard and really expands the size of the definition. I think it is still worthwhile to try when writing for a general audience because algebraic structure is everywhere and very useful to recognize for people who are interested in rigorously manipulating abstraction, i.e. programmers.

I agree; my "aka" wasn't meant as criticism. It's easy to get lost in the longer definitions, so I was just restating it directly in the hopes that one or the other - or the combination - will be clear to most people.

Though I'm not sure "abstract algebra jargon storm" properly describes use of "associative" and "identity" - I remember learning about the "associative property of multiplication" and such in elementary school and my wife confirms she had similar experience.

Reply on news.ycombinator.com