On Fri, Nov 13, 2009 at 1:10 PM, Stephen Tetley wrote:

...

Magicloud Magiclouds wrote:

...

...

That is OK. Since understand the basic concept of monoid (I mean the thing in actual math), the idea here is totally not hard for me. But the sample here does not show why (or how) we use it in programming, right?

Hi Magicloud

Conal Elliott has an interesting paper about designing your programs in relation to the standard type classes:.

http://conal.net/papers/type-class-morphisms/

Thinking about the data structures and functions in your program with regards the standard classes is very useful useful for clarifying your design. And certainly if you decide your data structure fits the Monoid interface then you will be presenting it to others who use your program in the 'standard vocabulary'. But even for Monoid which seemingly presents a simple interface (mempty, mappend) deciding whether the _container_ you have is naturally a monoid can be difficult.

A personal example, I've been developing a drawing library for a couple of months and still can't decide whether a bounding box should be a monoid (mempty, append) or a groupoid (just append) where append in both cases is union. Even though I haven't resolved this problem, having the framework of monoid versus groupoid at least gives me the _terminology_ to consider the problem.

Watch out, in more common parlance, having just an binary operation is a magma, while having a category with full inverses yields a groupoid. I haven't seen many people use the older groupoid term for magmas, if only because they started to have naming conflicts with the category theory people, and Bourbaki's 'magma' was available and unambiguous. =) And of course magma is not to be confused with the notion of a semigroup, which is a binary associative operation, and is therefore much more similar to a monoid in that all it lacks is a unit. -Edward Kmett

Best wishes

Stephen _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Stephen Tetley wrote:

Hi Edward

Many thanks.

I've mostly used groupoid for 'string concatenation' on types that I don't consider to have useful empty (e.g PostScript paths, bars of music...), as string concatenation is associative it would have been better if I'd used semigroup in the first place (bounding box union certainly looks associative to me as well).

Are magma and semigroup exclusive, i.e. in the presence of both a Magma class and a Semigroup class would it be correct that Magma represents only 'magma-op' where op isn't associative and Semigroup represents 'semigroup-op' where the op is associative?

Magma = exists S : Set , exists _*_ : (S,S)->S Semigroup = exists (S,*) : Magma , forall a b c:S. a*(b*c) = (a*b)*c Monoid = exists (S,*,assoc) : Semigroup , exists e:S. forall a:S. e*a = a = a*e Group = exists (S,*,assoc,e) : Monoid , forall a:S. exists a':S. a'*a = e = a*a' Personally, I don't think magmas are worth a type class. They have no structure and obey no laws which aren't already encoded in the type of the binop. As such, I'd just pass the binop around. There are far too many magmas to warrant making them implicit arguments and trying to deduce which one to use based only on the type of the carrier IMO. But if we did have such a class, then yes the (Magma s) constraint would only imply the existence of a binary operator which s is closed under, whereas the (Semigroup s) constraint would add an additional implication that the binary operator is associative. And we should have Semigroup depend on Magma since every semigroup is a magma. Unfortunately, Haskell's type classes don't have any general mechanism for stating laws as part of the class definition nor providing proofs as part of the instance.

When I decided to use a Groupoid class, I was being a bit lazy-minded and felt it could represent a general binary op that _doesn't have to be_ associative but potentially could be.

But groupoids do have to be associative (when defined). They're just like groups, except that the binop can be a partial function, and instead of a neutral element they have the weaker identity criterion (if a*b is defined then a*b*b' = a and a'*a*b = b). Groupoids don't make a lot of sense to me as "string concatenation"-like because of the inversion operator. Some types will support the idea of "negative letters" without supporting empty strings, but I can't think of any compelling examples off-hand. Then again, I deal with a lot of monoids which aren't groups and a lot of semirings which aren't rings, so I don't see a lot of inversion outside of the canonical examples. -- Live well, ~wren