On 12/20/12 6:42 AM, Christopher Howard wrote:
code:
--------
instance Category Integer where
id = 1
(.) = (*)
-- and
instance Category [a] where
id = []
(.) = (++)
-------
But these lead to kind mis-matches.
As mentioned in my other email (just posted) the kind mismatch is
because categories are actually monoid-oids[1] not monoids. That is:
class Monoid (a :: *) where
mempty :: a
mappend :: a -> a -> a
class Category (a :: * -> * -> *) where
id :: a i j
(.) :: a j k -> a i j -> a i k
Theoretically speaking, every monoid can be considered as a category
with only one object. Since there's only one object/index, the types for
id and (.) basically degenerate into the types for mempty and mappend.
Notably, from this perspective, each of the elements of the carrier set
of the monoid becomes a morphism in the category--- which some people
find odd at first.
In order to fake this theory in Haskell we can do:
newtype MonoidCategory a i j = MC a
instance Monoid a => Category (MonoidCategory a) where
id = MC mempty
MC f . MC g = MC (f `mappend` g)
This is a fake because technically (MonoidCategory A X Y) is a different
type than (MonoidCategory A P Q), but since the indices are phantom
types, we (the programmers) know they're isomorphic. From the category
theory side of things, we have K*K many copies of the monoid where K is
the cardinality of the kind "*". We can capture this isomorphism if we like:
castMC :: MonoidCategory a i j -> MonoidCategory a k l
castMC (MC a) = MC a
but Haskell won't automatically insert this coercion for us; we gotta do
it manually. In more recent versions of GHC we can use data kinds in
order to declare a kind like:
MonoidCategory :: * -> () -> () -> *
which would then ensure that we can only talk about (MonoidCategory a ()
()). Unfortunately, this would mean we can't use the Control.Category
type class, since this kind is more restrictive than (* -> * -> * -> *).
But perhaps in the future that can be fixed by using kind polymorphism...
[1] The "-oid" part just means the indexing. We don't use the term
"monoidoid" because it's horrific, but we do use a bunch of similar
terms like semigroupoid, groupoid, etc.
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
