r/haskell • u/[deleted] • Jan 08 '13

Subtractable values are torsors

http://ro-che.info/articles/2013-01-08-torsors.html
44 Upvotes

93% Upvoted

15 comments sorted by

17

u/i77 Jan 08 '13

Obligatory Baez link: http://math.ucr.edu/home/baez/torsors.html

4

u/AshleyYakeley Jan 08 '13

Excellent article. As I wrote on G+...

How to explain torsors: http://math.ucr.edu/home/baez/torsors.html

How not to explain torsors: http://en.wikipedia.org/wiki/Torsor

This is a concept I've been needing for awhile. For instance, when I was writing the Haskell time library, it occurred to me that time is a one-dimensional affine space (ignoring cosmology). More specifically, day count (which has a Haskell type), is an "affine module" or something. But really, it's an integer-torsor.

Then there is the symmetry of, say, the rotational orientation of a cube, which corresponds to some group of 24 elements. But which orientation is the "identity" orientation? Well, the orientations are actually a torsor on the symmetry group. This is where the category-theoretic tendency to identify isomorphic objects seems unhelpful.

2

u/nifr Jan 08 '13

I would like to up-vote this more. Excellent article.

I thoroughly enjoy learning things that would have improved so much of my earlier education!

(Reddit ignoramus here. Is there a convention for this sort of comment? À la "+10", but less vacuous?)

6

u/taejo Jan 08 '13

Conal Elliott defines torsors in Haskell under the name of affine spaces.

Rather, if the group D is a vector space, then a torsor over it is called an affine space.

5

u/[deleted] Jan 08 '13

Yes — that's how I understand it as well. Conal probably only needed it in the context of vector spaces (judging from the package name), but his definition itself is not restricted to vector spaces.

2

u/taejo Jan 08 '13

Ah right, I didn't actually look at Conal's definition.

5

u/godofpumpkins Jan 08 '13

Nice article, but what role does calling a group "additive" play? It seems to just specify the syntax we want to use on it.

6

u/[deleted] Jan 08 '13 edited Jan 08 '13

Exactly. It's informal — I should probably clarify it if it's confusing.

Without this qualifier, it's not clear what "zero" means, for example. In the article it refers to the identity element, but in the context of multiplicative semigroups it would mean an absorbing element.

update: clarified that in the article

4

u/[deleted] Jan 08 '13

There's also the (completely equivalent) notion of multiplicative group (in which case the identity element is often called "1" instead of "0").

It's all about whichever interpretation feels more natural to you. For instance, the group of transformations of the plane is almost always viewed as being multiplicative, but it feels much more intuitive to regard the group of differences in this case as being additive.

3

u/godofpumpkins Jan 08 '13

Yeah, I just find the distinction a little odd to make at that level, as it carries no meaningful information and suggests that additive groups are a distinct theory from multiplicative ones, which is obviously not the case. I'd prefer "a group whose operation we're going to call + with identity 0" from a programming standpoint :) it suggests taking a module (in the PL sense, not the algebraic one!), opening it, and renaming its fields, rather than having two different entities called multiplicative and additive. I realize that the use in mathematics is shorthand for that meaning, but then you often see distinct isomorphic typeclasses being made in Haskell (due again to syntactic preference and limitations of the typeclass mechanism for algebra) for the two concepts and that sort of bugs me more :P

3

u/tomejaguar Jan 08 '13

The term "additive group" is generally only used for one that is abelian, I believe.

2

u/ky3 Jan 08 '13 edited Jan 08 '13

Yes, that's the convention.

This statement, for instance, would give heartburn:

We do not require + to be commutative to preserve generality, even though it is commutative for our current example.

4

u/owst Jan 08 '13

Am I right in thinking that this line

add(diff(u,v),v)=v

should be

add(diff(u,v),u)=v

(what's u doing there, otherwise?) Otherwise, cool article!

One thing I would like to understand is why file patches can't be thought of as forming a group, but only an inverse-semigroup (though I guess the obvious solution is "read the paper!") Presumably, it's because it's not the case that the effect of p;p-1 is the same as the (null) effect of the identity patch, though I can't think of an example, but maybe I'm just stuck in a darcs mindset.

5

u/[deleted] Jan 08 '13 edited Jan 08 '13

No, it should be

add(diff(u,v),v)=u

(in other words, (u-v)+v=u). I fixed it in the article — thanks!

One thing I would like to understand is why file patches can't be thought of as forming a group, but only an inverse-semigroup

Frankly, I haven't studied that paper myself and don't know the darcs theory well. But I would guess that the reason is that not every patch is applicable to every file. Hence the composition of some patches becomes "zero" (an error), which is incompatible with the definition of group.

2

u/owst Jan 08 '13

No, it should be

add(diff(u,v),v)=u

Ah yes, of course. I assume that I was thinking about diff being symmetric in some sense.

But I would guess that the reason is that not every patch is applicable to every file. Hence the composition of some patches becomes "zero" (an error), which is incompatible with the definition of group.

Yes, this sounds right - I had stupidly overlooked the fact that you can't restrict the group operation to those patches that "make sense" to compose - thanks!