Subtractable values are torsors

A group is an abstraction for things that can be «added» and «subtracted» (in some sense).

Most of the groups that programmers deal with are numeric, although some interesting groups arise in graphics and cryptography.

If we only require that things can be added, but not subtracted, we get semigroups and monoids (the difference is that a monoid also has a «zero» element). These are plentiful, with applications ranging from diagrams to regular expressions.

The reason is, of course, that addition is very natural — we can consider any way to combine objects together an addition as soon as it is associative — while subtraction, the inverse of addition, often doesn’t make sense.

Dates

But there are also things that can be subtracted, but not added. The simplest example is dates. You can subtract two dates to get the time interval between them, but you cannot add two dates. It doesn’t make sense to ask what today plus tomorrow is. You could try to add the numeric values corresponding to the dates and convert the answer back to a date, but the result would depend on whether you count from the start of the Common Era, the Unix epoch, or something else.

While adding two dates is not possible, it is possible to add a time interval to a date («five days from today»). This suggests that we should not confound dates and time intervals — they are different types of values.

For example, in the Haskell time package, there are types UTCTime and NominalDiffTime, and the following functions:

addUTCTime :: NominalDiffTime -> UTCTime -> UTCTime
diffUTCTime :: UTCTime -> UTCTime -> NominalDiffTime

Time intervals can also be added and subtracted, as witnessed by the Num NominalDiffTime instance.

Ask mathematics

What is the mathematical notion that characterizes dates? It should involve two sets: the set \(V\) of values and the set \(D\) of value differences.

The set \(D\) must form an additive group, so that we can add and subtract the differences. (The word «additive» means that we assume that the group operation, identity element and inverse operation are called \(+\), \(0\) and \(−\) respectively. In group theory it is more common to call them \(\cdot\), \(1\) and \({}^{-1}\).)

Thus we have the “zero” difference \(0\in D\) and operations \(+\colon D\times D\to D\), \(-\colon D\to D\) which satisfy the usual group laws:

\(+/0\) (identity element)

\(0+x=x+0=x\)

\(+/+\) (associativity)

\((x+y)+z=x+(y+z)\)

\(+/−\) (inverse element)

\(x+(−x)=(−x)+x=0\)

(We can write \(x−y\) as a shorthand for \(x+(−y)\).)

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

We need to be able to add a difference to a value. Thus, we need a function \(\mathrm{add}:D\times V\to V\). We would expect it to play well with the group structure of \(D\):

\(\mathrm{add}/0\)

\(\mathrm{add}(0,v)=v\)

\(\mathrm{add}/+\)

\(\mathrm{add}(x+y,v)=\mathrm{add}(x,\mathrm{add}(y,v))\)

An alternative view on these laws is that the curried version of \(\mathrm{add}\), \(\mathrm{curry}(\mathrm{add}):D→(V→V)\), is a group homomorphism from \(D\) to the group of bijections on \(V\).

The mathematical abstraction corresponding to our \(\mathrm{add}\) function is an action of group \(D\) on the set \(V\). But it doesn’t yet capture the fact that we can subtract two values to get a difference. For that we need a function \(\mathrm{diff}:V×V→D\) inverse to \(\mathrm{add}\):

\(\mathrm{diff}/\mathrm{add}\)

\(\mathrm{diff}(\mathrm{add}(x,v),v)=x\)

\(\mathrm{add}/\mathrm{diff}\)

\(\mathrm{add}(\mathrm{diff}(u,v),v)=u\)

If such a function exists, the set \(V\) is called a torsor over the group \(D\).

Thus, it is the mathematical notion of torsor that characterizes subtractable values.

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

Other examples

Points

Another simple example of a torsor is points. In linear algebra we get used to conflating points and vectors, because we consider vectors originating at zero.

But the geometrical intuition suggests that vectors do not have to be tied to zero. A vector is a directed segment which can be freely translated (shifted) on the plane (or in the space).

We can subtract two points to get a vector from one point to another. We can add a vector to a point, by translating it so that its origin becomes the given point. The end point of the vector then becomes the result of addition.

Vectors form an additive group, and points form a torsor over the vectors.

Like with dates, results of torsor operations on points and vectors do not depend on (and do not require the existence of) a coordinate system, while the «sum» of two points will change if you change the origin.

Files

There are also some examples that look very much like torsors, but do not satisfy all the laws.

One of such examples is files. The difference of two files is what we call a patch, or a diff. We can diff two files and apply the resulting patch to a third file («cherry-picking»).

Although patches do not form a group, they can be modelled as inverse semigroups. This motivates us to consider torsors based on inverse semigroups rather than on groups.

Haskell dialects

Haskell dialects can be considered as a torsor-like structure over Haskell extensions. We can add extensions to languages:

\[\mathrm{add}(\mathrm{RankNTypes}+\mathrm{GADTs}−\mathrm{MonomorphismRestriction}, \mathrm{Haskell2010}).\]

We can also subtract two languages to find out the difference between them in terms of extensions: \[ \begin{align*} \mathrm{diff}(\mathrm{Haskell2010}, \mathrm{Haskell98}) & = \mathrm{DoAndIfThenElse} \\ & +\mathrm{PatternGuards} \\ & +\mathrm{ForeignFunctionInterface} \\ & +\mathrm{EmptyDataDecls} \\ & −\mathrm{NPlusKPatterns}. \end{align*} \]

Extensions do not form a group. The easiest way to see that is to observe that extensions are idempotent, i.e. \(X+X=X\) for any extension \(X\). However, in a group there is only one idempotent element, zero.

Extensions do form an inverse semigroup, though. Thus we again arrive at inverse semigroup torsors.

Acknowledgements

A recent discussion with Niklas Broberg about Haskell extensions motivated me to explore these concepts. His HIW’12 lightning talk on Haskell Modular Mindset is also relevant.

Oleksandr Manzyuk kindly pointed me to the concept of a torsor.