On Thu, Jun 06, 2013 at 08:41:47PM -0700, Frerich Raabe wrote:

On Jun 6, 2013, at 5:56 PM, Brent Yorgey wrote:

...

On Thu, Jun 06, 2013 at 05:27:11PM -0700, Frerich Raabe wrote:

...

I could do something like

data List a = Singleton a | Cons a (List a)

but before I go ahead I wonder: is there an existing Haskell package for this? Maybe even with prettier names than what I wrote above, and convenient functions for transforming from/to plain [] lists? It would probably be straightforward to write it myself, but because of that, I suspect that somebody else already did it. :-)

Yes, this exists in the semigroups package:

http://hackage.haskell.org/packages/archive/semigroups/0.9.2/doc/html/Data-L...

Awesome, thanks a lot for pointing this out! semigroups… I don't even know what that would be, pretty sure I wouldn't have found this by myself. :-}

A semigroup is simply a set with an associative binary operation. So all monoids are semigroups, but other things are semigroups as well; for example, 'max' is an associative binary operation on the real numbers, so this is a semigroup; but max has no identity element (there is no smallest real number) so it is not a monoid. Non-empty lists come up a lot when working with semigroups (technically this is because non-empty lists with (++) are the "free semigroup", i.e. the Mother Of All Semigroups) which is why they are in this package. If you want to learn more about monoids and semigroups and some ways they can be applied, you might be interested in my paper from last year's Haskell Symposium, "Monoids: Theme and Variations", which you can find at http://www.cis.upenn.edu/~byorgey/publications.html along with a link to a video and slides. -Brent