[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