Relating functors in Category Theory to Functor
Until recently, I've had difficulty relating the concept of a "functor"
from Category Theory to the class Functor in Haskell. I've figured out a
relationship that seems to make sense, but I wanted to check with the
list to make sure I'm not on the wrong track.
In Category Theory, a functor F between categories C and D has two
parts:
(1) a mapping F[ob] from the objects of C to the objects of D
(2) a mapping F[mor] from the morphisms of C to the morphisms of D
For any morphism f: a -> b in C, there is a morphism F(f): F(a) -> F(b)
in D. For two morphisms f and g in C, F(f . g) = F(f) . F(g) in D.
We can interpret Haskell as a category with types as objects and
functions as morphisms. For example, isDigit :: Char -> Bool.
So, for some Functor f, the type constructor f corresponds to F[ob], and
fmap to F[mor]. For any function g :: a -> b, fmap g :: f a -> f b, and
fmap (g . h) = fmap g . fmap h.
--
For two functors F, G: C -> D, there is a natural transformation tau
from F to G, if for every object a in C, there is morphism tau[a]: F(a)
-> G(a) in D.
In Haskell, natural transformations are polymorphic functions, tau :: f
a -> g a. For example, maybeToList :: Maybe a -> [a].
--
A monad is a functor, F: C -> C, plus two natural transformations mu:
F^2 -> F and eta: I -> F (I being the identity functor for C).
In Haskell, F[ob] becomes the type constructor, F[mor] becomes fmap (or
liftM), mu becomes join :: f (f a) -> f a, and eta becomes return :: a
-> f a.
So, am I on the right track here?
--
David Menendez
G'day all.
Quoting David Menendez
Until recently, I've had difficulty relating the concept of a "functor" from Category Theory to the class Functor in Haskell.
[...]
We can interpret Haskell as a category with types as objects and functions as morphisms. For example, isDigit :: Char -> Bool.
So, for some Functor f, the type constructor f corresponds to F[ob], and fmap to F[mor]. For any function g :: a -> b, fmap g :: f a -> f b, and fmap (g . h) = fmap g . fmap h.
Correct. Technically, Functor should probably be called Endofunctor, because it's actually a functor from the category Haskell to the category Haskell. That would probably just confuse things more, though. :-)
For two functors F, G: C -> D, there is a natural transformation tau from F to G, if for every object a in C, there is morphism tau[a]: F(a) -> G(a) in D.
In Haskell, natural transformations are polymorphic functions, tau :: f a -> g a. For example, maybeToList :: Maybe a -> [a].
Not quite. A natural transformation is a mapping between _functors_. In this case, maybeToList is a natural transformation between Maybe and []. Expressing this as a typeclass is left as an exercise, but here's a start: class (Functor f, Functor g) => NaturalTransformation ... where ...
A monad is a functor, F: C -> C, plus two natural transformations mu: F^2 -> F and eta: I -> F (I being the identity functor for C).
In Haskell, F[ob] becomes the type constructor, F[mor] becomes fmap (or liftM), mu becomes join :: f (f a) -> f a, and eta becomes return :: a -> f a.
Yup! Handily, all Haskell Functors are endofunctors, so Haskell monads don't need the extra constraint that F must be an endofunctor. Cheers, Andrew Bromage
This raises for me the more general question of, what should I read so that I can more easily get a handle on what Haskell's arrows and monads have to do with similar category-theory concepts? I can find plenty about Haskell's monads, and there seem to be plenty of computer science category theory texts (which some variation in terminology) but I'm not really sure where the two meet. -- Mark
For two functors F, G: C -> D, there is a natural transformation tau from F to G, if for every object a in C, there is morphism tau[a]: F(a) -> G(a) in D.
In Haskell, natural transformations are polymorphic functions, tau :: f a -> g a. For example, maybeToList :: Maybe a -> [a].
actually i think this is a good approximation. not all polymorphic functions are natural
hi, just a few silly remarks... ajb@spamcop.net wrote: transformations, but "simple" ones usually are.
Not quite. A natural transformation is a mapping between _functors_. In this case, maybeToList is a natural transformation between Maybe and []. Expressing this as a typeclass is left as an exercise, but here's a start:
class (Functor f, Functor g) => NaturalTransformation ... where ...
it is not a good idea to have a _class_ for natural transformations as they have little to do with overloading. there can be many different natural transformations between two functors, so it does not make sense to give them all the same name. -iavor
G'day all.
Quoting "Iavor S. Diatchki"
just a few silly remarks...
Not so silly...
actually i think this is a good approximation. not all polymorphic functions are natural transformations, but "simple" ones usually are.
I've found when studying category theory that expressing this stuff in Haskell REALLY helps. Haskell was a familiar notation, where category theory notation was not. Being able to freely translate between the two helps. In this case, recognising _which_ polymorphic functions are natural transformations help you understand what a natural transformation is. A natural transformation in Haskell is a function of the form: tau :: f a -> g a where f and g are specific Functors. In the book by Saunders MacLane, there was one remark about natural transformations which really helps. He noted that a natural transformation is one that's done
it is not a good idea to have a _class_ for natural transformations as they have little to do with overloading.
Indeed. If you actually want to get work done in Haskell, making a class for this is a bad idea. But then there are easier ways to do this, too: http://www.haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell My point is that Haskell is a good and (for most people on this mailing list) familiar notation for expressing these concepts. Cheers, Andrew Bromage
On Jun 29, 2004, at 6:46 PM, Iavor S. Diatchki wrote:
In Haskell, natural transformations are polymorphic functions, tau :: f a -> g a. For example, maybeToList :: Maybe a -> [a].
actually i think this is a good approximation. not all polymorphic functions are natural transformations, but "simple" ones usually are.
I think you have it backwards, unless you are thinking of a more general notion of polymorphism than parametric polymorphism. Ad hoc polymorphic functions may or may not be natural; you have to verify the naturality condition in each case. But every parametrically polymorphic function is a natural transformation, though the converse fails: not every natural transformation is parametrically polymorphic. In particular, some natural transformations are generic functions (polytypic), and their components (instantiations at a type) are not all instances of a single algorithm. I'm not sure if every natural transformation on endofunctors on a category modelling a Haskell-like language is denoted by either a parametric or generic term. Regards, Frank
hello, i was thinking of higher-order functions, which i think complicate things (i might be wrong though :-) for example: fix :: (a -> a) -> a is ploymorphic, but is it a natural tranformation? i belive it is in fact a di-natural transformation. -iavor
On Jun 29, 2004, at 6:46 PM, Iavor S. Diatchki wrote:
In Haskell, natural transformations are polymorphic functions, tau :: f a -> g a. For example, maybeToList :: Maybe a -> [a].
actually i think this is a good approximation. not all polymorphic functions are natural transformations, but "simple" ones usually are.
I think you have it backwards, unless you are thinking of a more general notion of polymorphism than parametric polymorphism.
Ad hoc polymorphic functions may or may not be natural; you have to verify the naturality condition in each case.
But every parametrically polymorphic function is a natural transformation, though the converse fails: not every natural transformation is parametrically polymorphic. In particular, some natural transformations are generic functions (polytypic), and their components (instantiations at a type) are not all instances of a single algorithm.
I'm not sure if every natural transformation on endofunctors on a category modelling a Haskell-like language is denoted by either a parametric or generic term.
Regards, Frank
participants (5)
-
ajb＠spamcop.net -
David Menendez -
Frank Atanassow -
Iavor S. Diatchki -
Mark Carroll