Proposition: each type is a category itself.
Ex: Int
is a category of all integers
under Hask.
Is that the case?
If so, what are homomorphisms in the category of Int
, or all possible morphism from Int->Int
?
How can define it?
edited:
--In the category of Hask
--Imagine, I have Str category just of strings under Hask, then:
Obj(Str) is Singelton
Hom (Str) is each string
Composition operation is (++) operator --in Haskell
Depends on what you mean by "type" and "is a category". If you take any concrete type in a programming language, there are only countably many possible values of that type, so you can just take the set of all values, and say that it is a discrete category C
, which has nothing but the identity morphisms.
Integers can be considered a category in many different ways:
Obj(C) = {*}
is the only object, each integer is a morphism, 0
is the identity morphism, +
is the composition).(a, b)
such that a <= b
. Reflexivity a <= a
are the identity morphisms. Transitivity is the composition.a|b
. Again, refl_a = a|a
are the identity morphisms, the fact that if a|b
and b|c
then a|c
gives the composition.If you are interested only in the type Int
, you can also build
many different categories out of it:
The simplest example: take Int
as the only object, take the identity function on Int
as the only morphism, done. That's a category, usually called 1
.
Somewhat less degenerate construction: the monoid of endomorphisms on Int
. Again take Int
as the only object of your category. Take as Hom[Int, Int]
the set of all terminating total functions which are implementable in Haskell (1) , define the composition on this hom-set as the ordinary composition of functions.
You can play with this construction a little: for example, you can consider partial functions, or only invertible functions (that would give a group of automorphisms, and therefore a very simple groupoid).
There are many other ways to define a category which "bears some relationship to Int
". It depends on what you want to do with it.
On your 'edit': That's just a special case of every monoid being a category with a single object. For integers, you can immediately build a handful of monoids:
(Int, +, 0)
(a+b
is the composition, 0
is the identity)(Int, *, 1)
(a*b
is the composition, 1
is the identity)(Int, bitwise Xor, 0)
(a xor b
is the composition, 0
the identity)(Int, bitwise And, 0xF...F)
, analogousYou obtain a category from a monoid always by the same construction: given a monoid (M, op, zero)
, take a structureless point {*}
as the single object, take M
as the set of morphisms, take zero
as the identity, op
as composition, and you obtain a category. This is simply because monoids are by definition the same as categories with a single object.
EDIT:
(1) Oh, wait, you'd need rather something like the equivalence classes modulo extensionality, otherwise even f . id
isn't the same as f
, and associativity wouldn't work either, even without the "help" of integer-overflows and other nasty things that happen on a real computer. Notice that the undecidability of properties like "does it terminate for all input values?" and "do these two functions return the same result for all inputs?" does not break the well-definedness.