[Haskell-beginners] Are functors in Haskell always injective?

[Brent Yorgey]

Ah, I suppose there are several ways to interpret the original
statement.  Natural language is ambiguous like that.  In any case, to
sum up:

* Mathematical functors from C to D must be defined on all objects and
  morphisms of C.

* In Haskell, instances of the Functor class are restricted to
  mathematical functors whose domain and codomain are both Hask.

* A consequence of Dimitri's observation is that there are even some
  mathematical Hask -> Hask functors which are not Functor instances!
  For example, any non-injective Hask -> Hask functor cannot be
  represented in Haskell.  Consider

    data ConstInt a = CI Int

  ConstInt may "seem" like it is not injective (it maps everything to
  Int) but that is not quite true.  In fact, it does not map
  everything to Int.  It maps, say, Bool to ConstInt Bool, and Char to
  ConstInt Char.  Despite being isomorphic (indeed, having exactly the
  same representation), ConstInt Bool and ConstInt Char are not equal
  types.  On the other hand, a type synonym like

    type ConstInt a = Int

  really is non-injective; but it cannot be made an instance of
  Functor.

-Brent

On Sat, Jul 05, 2014 at 12:21:52PM -0700, David Thomas wrote:
> As stated, it seems precisely true.  There was no implication that the
> domain still be Hask.
> 
> On Sat, Jul 5, 2014 at 10:34 AM, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
> > On Sat, Jul 05, 2014 at 11:51:10AM +0100, Julian Birch wrote:
> >> (Another beginner here)
> >>
> >> That's my understanding too.  Functors in Haskell have to operate on the
> >> whole of Hask, which isn't true of functors in general.
> >
> > As stated, this is not true: a functor F : C -> D must be defined on
> > *all* the objects of the category C.  I.e., it is still true that
> > functors in general must operate on the whole of their domain
> > category.  I think what you are getting at is that there are (lowercase-f) functors
> > whose domain is a *sub*category of Hask (such as the category of all
> > types having an Ord instance, with order-preserving functions as
> > morphisms) which cannot be extended to functors on all of Hask, and so
> > they are not (capital-F) Functors.
> >
> > -Brent
> >
> >> Equally, they have
> >> to map to a subset of Haskell (although that mapping could be isomorphic to
> >> Hask e.g. Identity Functor).  It's the first restriction that's the most
> >> problematic, since it prevents set from being a Functor.  This is fixable (
> >> http://okmij.org/ftp/Haskell/RestrictedMonad.lhs) but not part of "standard
> >> Haskell".  The second restriction basically just means you've got to do
> >> some book-keeping to get back to the original type.
> >>
> >> Julian
> >>
> >>
> >> On 5 July 2014 06:51, Dimitri DeFigueiredo <defigueiredo at ucdavis.edu> wrote:
> >>
> >> >  Oops! Sorry for the typos! Fixing that below.
> >> >
> >> >
> >> > Hi All,
> >> >
> >> > My understanding is that a functor in Haskell is made of two "maps".
> >> > One that maps objects to objects that in Hask means types into types (i.e.
> >> > a type constructor)
> >> > And one that maps arrows into arrows, i.e. fmap.
> >> >
> >> > My understanding is that a functor F in category theory is required to
> >> > preserve the domain and codomain of arrows, but it doesn't have to be
> >> > injective. In other words, two objects X and Y of category C (i.e. two
> >> > types in Hask) can be mapped into the same object Z (same type) in category
> >> > D. As long as the "homomorphism" law holds:
> >> >
> >> > F(f:X->Y) = F(f):F(X)->F(Y)
> >> >
> >> > However, I don't think there is any way this mapping of types cannot be
> >> > injective in Haskell. It seems that a type constructor, when called with
> >> > two distinct type will always yield another two **distinct** types. (E.g.
> >> > Int and Double yield Maybe Int and Maybe Double) So, it seems that Functors
> >> > in Haskell are actually more restrictive than functors can be in general.
> >> > Is this observation correct or did I misunderstand something?
> >> >
> >> >
> >> > Thanks!
> >> >
> >> >
> >> > Dimitri
> >> >
> >> > Em 05/07/14 02:42, Dimitri DeFigueiredo escreveu:
> >> >
> >> > Hi All,
> >> >
> >> > My understanding is that a functor in Haskell is made of two "maps".
> >> > One that maps objects to objects that in Hask means types into types (i.e.
> >> > a type constructor)
> >> > And one that maps arrows into arrows, i.e. fmap.
> >> >
> >> > My understanding is that a functor F in category theory is required to
> >> > preserve the domain and codomain of arrows, but it doesn't have to be
> >> > injective. In other words, two objects X and Y of category C (i.e. two
> >> > types in Hask) can be mapped into the same object Z (same type) in category
> >> > Z. As long as the "homomorphism" law holds:
> >> >
> >> > F(f:X->Y) = F(f):F(X)->F(Y)
> >> >
> >> > However, I don't think there is any way this mapping of types cannot be
> >> > injective in Haskell. It seems that a type constructor, when called with
> >> > two distinct type will always yield another two *distinct* types. (E.g. Int
> >> > and Fload yield Maybe Int and Maybe) So, it seems that Functors in Haskell
> >> > are actually more restrictive than functors can be in general. Is this
> >> > observation correct or did I misunderstand something?
> >> >
> >> >
> >> > Thanks!
> >> >
> >> >
> >> > Dimitri
> >> >
> >> >
> >> > _______________________________________________
> >> > Beginners mailing list
> >> > Beginners at haskell.org
> >> > http://www.haskell.org/mailman/listinfo/beginners
> >> >
> >> >
> >> >
> >> > _______________________________________________
> >> > Beginners mailing list
> >> > Beginners at haskell.org
> >> > http://www.haskell.org/mailman/listinfo/beginners
> >> >
> >> >
> >
> >> _______________________________________________
> >> Beginners mailing list
> >> Beginners at haskell.org
> >> http://www.haskell.org/mailman/listinfo/beginners
> >
> > _______________________________________________
> > Beginners mailing list
> > Beginners at haskell.org
> > http://www.haskell.org/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners