Suppose you're defining a Point class, and you're trying to write the subtraction operator. What type should it return? Another Point? Or should you invent a new class called Vector? Vectors and Points have exactly the same machine representation, so it seems kind of a waste to create two classes. And yet you have this vague feeling that Vectors and Points really are different, and it might be a good idea to maintain different types for different things. Who knows, maybe it'll catch a mistake in your math. On the other hand, maybe you'll end up having to convert between them all the time, and it'll just end up being annoying rather than helpful.
Here's another example that's a bit more clear cut. Suppose you're working with a version control system, and you want to represent both documents and the differences between documents. In theory both of these could be represented by strings (for example the output from the unix diff command is just plain text). It makes sense to subtract two documents to get a diff, and to add a diff to a document to get a new, patched document. But it makes no sense to add two documents, or to subtract a diff and a document. In this example, it's pretty obvious that you want to keep the types separate, even if the physical representation is the same.
If you've ever found yourself designing a program that has these kinds of concepts, you might want to read about torsors. They're a concept from math that generalizes the idea of things as opposed to differences between things. My favorite quote from that article:
An affine space is like a vector space that has forgotten its origin. A torsor is like a group that has forgotten its identity.
To me, the interesting thing about the concept of a torsor is that it makes it clear that there's a mathematical justification for why addition and subtraction (or multiplication and division) might not have the same types. I love stuff like this. It makes me want to write a Torsor type class in haskell, just because it feels right, even though I have no immediate use for it.
Posted on March 30, 2006 11:13 AM
More languages articles
i hope people aren't going to go away thinking diff is an example of a torsor :I
Posted by: ian at March 31, 2006 06:05 PMWhy, may I ask, is it not?
Posted by: crzwdjk at April 1, 2006 12:39 PMassuming theres a diff that allows you to add 'hello' to the start of any document, its difficult to see what kind of document when having this diff applied to it would result in the empty document.
Posted by: ian at April 2, 2006 09:17 AMI think it's supposed to be the other way around, with documents being the torsor, and diffs just being a plain old group (assuming no such thing as rejected diffs). After all, there is an identity diff, and no special document, since the only thing we care about is the difference between two documents. So I think it is still valid.
Posted by: crzwdjk at April 4, 2006 03:36 AMif it is a torsor then my 'hello' diff should have an inverse. applying this inverse to the empty document will give another document. its this document which will result in the empty document when my 'hello' diff is applied to it.
theres nothing special about the empty document. i just use it as an example of a document.
The linked explanation made no mention whatsoever of inverses, and only talked about groups. And a group does not imply having an inverse, for example multiplication in the set of integers, or n by n matrices and multiplication, or string concatenation. As far as I understood it, the whole torsor idea applies to plain old groups, and inverses are not needed.
Posted by: crzwdjk at April 5, 2006 02:53 AMhttp://en.wikipedia.org/wiki/Group_(mathematics)#Basic_definitions
;)
One could draw an analogy between documents and the notion of temperature as explained in John Baez's article. The empty document would then correspond to absolute zero.
(This would imply that the set that diffs constitute is the same as the group of documents, but I am stepping beyond the limits of my understanding here!)
-K
Posted by: Kaushik at April 10, 2006 02:05 AMIn the case of points and vectors, the distinction goes even deeper. If you transform the space, then points and vectors transform differently.
As an example: Take two points. Now move the origin. The points "move" relative to the origin, but the difference between the two points (which is a vector) does not change at all:
(p1 + o) - (p2 + o) = p1 - p2
Posted by: Pseudonym at May 6, 2006 07:28 PM... and even deeper ...
in 3D computer graphics we know that tangents transform differently from normals (tangents transform like points), and in mechanics we know that torques transform differently than forces.
The underlying deepness is that you really need to go beyond the degenerate representations using vectors and matrices, to a graded space that keeps all the different kinds of 'vectors' separate: scalars, pseudo-scalars, pseudo-vectors, vectors, directed volumes, etc.
You need a Clifford Algebra.
Mik
Of course, it's true that Baez's example of temperatures as forming a torsor is misleading. Indeed, if there were no absolute 0, then they would form such a torsor; but the presence of absolute zero makes temperatures a copy of R_+, not of R. Remedy: Define torsors for semi-groups and other algebraic structures (as Baez almost does for rings when he talks about dilation and translation at the end of the linked article).
Posted by: JadeNB at August 24, 2008 05:13 PM