Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Are functors in Haskell always injective? (Brent Yorgey)
2. Re: Are functors in Haskell always injective? (Brent Yorgey)
3. Re: Are functors in Haskell always injective? (David Thomas)
4. Re: Are functors in Haskell always injective? (Brent Yorgey)
5. Re: Are functors in Haskell always injective? (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Sat, 5 Jul 2014 13:27:37 -0400
From: Brent Yorgey <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Are functors in Haskell always
injective?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Jul 05, 2014 at 02:51:07AM -0300, Dimitri DeFigueiredo wrote:
>
> 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?
Yes, that's correct.
-Brent
------------------------------
Message: 2
Date: Sat, 5 Jul 2014 13:34:08 -0400
From: Brent Yorgey <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Are functors in Haskell always
injective?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
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 <[email protected]> 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
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/beginners
> >
> >
> >
> > _______________________________________________
> > Beginners mailing list
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/beginners
> >
> >
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 3
Date: Sat, 5 Jul 2014 12:21:52 -0700
From: David Thomas <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Are functors in Haskell always
injective?
Message-ID:
<cajudvcgj4nqdxquyqnayqtvhqen_gu8ouqkdikg9vv+ygm_...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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 <[email protected]> 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 <[email protected]> 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
>> > [email protected]
>> > http://www.haskell.org/mailman/listinfo/beginners
>> >
>> >
>> >
>> > _______________________________________________
>> > Beginners mailing list
>> > [email protected]
>> > http://www.haskell.org/mailman/listinfo/beginners
>> >
>> >
>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 4
Date: Sat, 5 Jul 2014 15:50:47 -0400
From: Brent Yorgey <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Are functors in Haskell always
injective?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
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 <[email protected]> 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 <[email protected]>
> >> 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
> >> > [email protected]
> >> > http://www.haskell.org/mailman/listinfo/beginners
> >> >
> >> >
> >> >
> >> > _______________________________________________
> >> > Beginners mailing list
> >> > [email protected]
> >> > http://www.haskell.org/mailman/listinfo/beginners
> >> >
> >> >
> >
> >> _______________________________________________
> >> Beginners mailing list
> >> [email protected]
> >> http://www.haskell.org/mailman/listinfo/beginners
> >
> > _______________________________________________
> > Beginners mailing list
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 5
Date: Sun, 6 Jul 2014 06:38:57 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Are functors in Haskell always
injective?
Message-ID:
<CAPY+ZdR=7w48xgkljfbe3mdpytpqpzux7legmq1uo4ngd9n...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Sun, Jul 6, 2014 at 12:27 AM, Brent Yorgey <[email protected]>
wrote:
> On Sat, Jul 05, 2014 at 02:51:07AM -0300, Dimitri DeFigueiredo wrote:
> >
> > 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?
>
> Yes, that's correct.
Why is that correct? How would you show that?
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140706/b20dcd64/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 73, Issue 4
****************************************
