[Haskell-cafe] Re: Haskell-Cafe Digest, Vol 10, Issue 3

Frank Atanassow franka at cs.uu.nl
Fri Jun 11 09:15:49 EDT 2004


First, concerning your question about monads and multiplication: a 
monad on category C is exactly a monoid object in the category [C->C] 
of endofunctors on C, and natural transformations between them. A 
monoid in a category is, as you expect, an object X with arrows 
m:X*X->X and u:1->X satisfying some laws, where * is the monoidal 
tensor and 1 is its unit. In [C->C], * is functor composition and 1 is 
the identity functor; so m becomes `join' and u becomes `return'. See 
the Example at the bottom of page 75 in Chapter 4 of [1].

On Jun 10, 2004, at 4:23 PM, Ron de Bruijn wrote:
>> For a counter-example, think of the dual category
>> Set^{op}.  A morphism
>> f : a -> b in that category means that there is a
>> function f^{op} : b -> a
>>
>> where a and b are sets, however f probably isn't a
>> function at all.
> Well, what is it then?

The short answer is: it's the formal dual of a function, and that's 
all. You will have to get used to this fact about categorical duality, 
that it's just a formal construction and has no deep meaning in and of 
itself.

The short long answer is: it's an antifunction, or a predicate 
transformer (I think).

What is an antifunction? Well, if you factor a function as a surjection 
followed by a bijection followed by an injection (as you can always do 
uniquely in Set using image factorization), then you can understand a 
function as something which identifies, then renames, then adjoins 
elements of a set. If you turn this map around, and look at what 
happens to the elements on their way home, you can see that what 
happens is some elements get deleted, then renamed and then copied. So 
a function identifies, renames and adjoins while an antifunction 
deletes, renames and copies.

To formalize this perspective, you can view a(n antiset) as a boolean 
algebra using the faithful embedding of Set^{op} in Set via the 
contravariant powerfunctor. The action on arrows turns an antifunction 
into what I imagine is called a predicate transformer. This is nicely 
explained in Vaughan Pratt's paper [2] which, BTW, is about the Chu 
construction which I mentioned in my last post to Jerzy.

> Is the following a good summary?
> A multiplication is just a name for an operation that
> is defined or not defined for each mathematical
> construction in terms of to which laws the operation
> should comply. The laws are then things like
> communativity and so on.

Multiplication is just a name often used for any operation which is 
typically but not always associative and has right and left units, and 
is perhaps also commutative. Addition is exactly the same. If one has 
two operations which satisfy these properties, then one often 
distinguishes them by saying one is "addition" and the other is 
"multiplication".

It is all informal convention; the important things are the laws.

[1] Andrea Asperti and Giuseppe Longo. Categories, Types and 
Structures. 1990. Available here: 
http://www.di.ens.fr/users/longo/download.html

[2] Vaughan Pratt. The Stone Gamut: A Coordinatization of Mathematics. 
In Proc. LICS '95, 1995.
http://boole.stanford.edu/pub/gamut.ps.gz

Regards,
Frank



More information about the Haskell-Cafe mailing list