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: Pattern matching over functions (Brent Yorgey)
2. Re: Pattern matching over functions (Giacomo Tesio)
3. Re: Pattern matching over functions (Alec Story)
4. Re: Pattern matching over functions (Brent Yorgey)
----------------------------------------------------------------------
Message: 1
Date: Wed, 7 Dec 2011 09:42:01 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Pattern matching over functions
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Wed, Dec 07, 2011 at 11:34:28AM +0100, Giacomo Tesio wrote:
> Hi Haskellers,
>
> I'm wondering why, given that functions and referential transparency are
> first class citizens in haskell, it isn't possible to write a mapping
> function this way:
>
> f1 :: a -> b
>
> f2 :: a -> b
>
> f3 :: c -> a -> b
>
> map :: (a -> b) -> T a -> T b
> map f1 = anEquivalentOfF1InTCategory
> map f2 = anEquivalentOfF2InTCategory
> map f3 $ c = anEquivalentOfF3withCInTCategory
> map unknown = aGenericMapInTCategory
>
> Is it "just" the implementation complexity of the feature in ghc that
> prevents this?
> Or is it "conceptually" wrong?
>
> At a first look, I thought that most of complexity here should be related
> to function's equality, but than I thought that the function full name
> should uniquely map from the category of meanings in the programmer mind to
> the category of implementations available to the compiler's.
It is preciesly *because* of referential transparency that you cannot
do this. Suppose that
f1 = \x -> bar x (5*x)
then
map (\x -> bar x (5*x))
is supposed to be equivalent to 'map f1'. You might not think that is
too bad -- it is obvious that is the same as f1's definition. But
what about
map (id (\z -> bar z (2*x + 3*x)))
? This is also required to be the same as 'map f1'. But now you have
to know about distributivity of multiplication over addition in order
to tell. This gets arbitrarily complicated (and, in fact,
undecidable) very quickly.
-Brent
------------------------------
Message: 2
Date: Wed, 7 Dec 2011 18:10:01 +0100
From: Giacomo Tesio <[email protected]>
Subject: Re: [Haskell-beginners] Pattern matching over functions
Cc: [email protected]
Message-ID:
<CAHL7psGM8MVw62w0TVwPATR6YV+K_nVaThUfjriUZ=-ticw...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Brent, thanks for your answer.
I don't get it, though...
Looks like
> id (\z -> bar z (2*x + 3*x))
is actually different from
> f1 -> \x -> bar x (5*x)
as in the first x can only be a closure, while in the second is an argument.
Supposing that it's just a typo and you did mean id (\z -> bar z (2*z +
3*z)) I see how it could be very complex, but still seem to me
(theoretically?) decidable.
What I'm missing?
Nevertheless, while I would see an extreme value in a compiler that is able
to understand that "id (\z -> bar z (2*z + 3*z)) == f1" is True, it's not
my target.
I would find already very useful a compiler that is able to understand id f
= f, that (\x -> 3 + x) == (\y = 3 + y) == (+3) even if it isn't able to
see that (+3) == (\x -> 2 + 1 + x).
This would improve greatly the power of Functors (at least as I understood
them :-D)
Don't you think?
Giacomo
On Wed, Dec 7, 2011 at 3:42 PM, Brent Yorgey <[email protected]> wrote:
> On Wed, Dec 07, 2011 at 11:34:28AM +0100, Giacomo Tesio wrote:
> > Hi Haskellers,
> >
> > I'm wondering why, given that functions and referential transparency are
> > first class citizens in haskell, it isn't possible to write a mapping
> > function this way:
> >
> > f1 :: a -> b
> >
> > f2 :: a -> b
> >
> > f3 :: c -> a -> b
> >
> > map :: (a -> b) -> T a -> T b
> > map f1 = anEquivalentOfF1InTCategory
> > map f2 = anEquivalentOfF2InTCategory
> > map f3 $ c = anEquivalentOfF3withCInTCategory
> > map unknown = aGenericMapInTCategory
> >
> > Is it "just" the implementation complexity of the feature in ghc that
> > prevents this?
> > Or is it "conceptually" wrong?
> >
> > At a first look, I thought that most of complexity here should be related
> > to function's equality, but than I thought that the function full name
> > should uniquely map from the category of meanings in the programmer mind
> to
> > the category of implementations available to the compiler's.
>
> It is preciesly *because* of referential transparency that you cannot
> do this. Suppose that
>
> f1 = \x -> bar x (5*x)
>
> then
>
> map (\x -> bar x (5*x))
>
> is supposed to be equivalent to 'map f1'. You might not think that is
> too bad -- it is obvious that is the same as f1's definition. But
> what about
>
> map (id (\z -> bar z (2*x + 3*x)))
>
> ? This is also required to be the same as 'map f1'. But now you have
> to know about distributivity of multiplication over addition in order
> to tell. This gets arbitrarily complicated (and, in fact,
> undecidable) very quickly.
>
> -Brent
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111207/6b52b332/attachment-0001.htm>
------------------------------
Message: 3
Date: Wed, 7 Dec 2011 18:35:01 -0500
From: Alec Story <[email protected]>
Subject: Re: [Haskell-beginners] Pattern matching over functions
To: Giacomo Tesio <[email protected]>
Cc: [email protected]
Message-ID:
<CAKcn5spzg0ZBNz4CLO=rjxmnuvxahi9_anablqwj_g-ren_...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Dec 7, 2011 at 12:10 PM, Giacomo Tesio <[email protected]> wrote:
> Hi Brent, thanks for your answer.
>
> I don't get it, though...
>
> Looks like
>
>> id (\z -> bar z (2*x + 3*x))
>
>
> is actually different from
>
>> f1 -> \x -> bar x (5*x)
>
>
> as in the first x can only be a closure, while in the second is an
> argument.
>
> Supposing that it's just a typo and you did mean id (\z -> bar z (2*z +
> 3*z)) I see how it could be very complex, but still seem to me
> (theoretically?) decidable.
> What I'm missing?
>
But what if we embedded an undecidable problem in the function? For
example, \x -> if haltingProblem then x (5*x) else x (4*x). There's no way
to decide whether that function is the same or not.
>
> Nevertheless, while I would see an extreme value in a compiler that is
> able to understand that "id (\z -> bar z (2*z + 3*z)) == f1" is True, it's
> not my target.
>
> I would find already very useful a compiler that is able to understand id
> f = f, that (\x -> 3 + x) == (\y = 3 + y) == (+3) even if it isn't able to
> see that (+3) == (\x -> 2 + 1 + x).
>
>
> This would improve greatly the power of Functors (at least as I understood
> them :-D)
> Don't you think?
>
>
> Giacomo
>
That would be nice, but it's awkward to include functionality that relies
on partial execution of code that may or may not terminate. I'm not sure
how useful alpha substitution like you ask for would be; I don't think it
would fix the problem you raised at first.
--
Alec Story
Cornell University
Biological Sciences, Computer Science 2012
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111207/2b953b5e/attachment-0001.htm>
------------------------------
Message: 4
Date: Thu, 8 Dec 2011 01:14:39 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Pattern matching over functions
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Wed, Dec 07, 2011 at 06:10:01PM +0100, Giacomo Tesio wrote:
> Hi Brent, thanks for your answer.
>
> I would find already very useful a compiler that is able to understand id f
> = f, that (\x -> 3 + x) == (\y = 3 + y) == (+3) even if it isn't able to
> see that (+3) == (\x -> 2 + 1 + x).
But then we would lose referential transparency.
> This would improve greatly the power of Functors (at least as I understood
> them :-D)
> Don't you think?
Well... I suppose it would make things more expressive (although I
think "greatly" is overstating things), but at the terrible cost of
losing referential transparency, and probably also parametricity
(although I have not thought about it carefully). I, for one, am not
willing to give up these beautiful and powerful reasoning tools just
for a little gain in expressivity.
-Brent
>
>
> Giacomo
>
> On Wed, Dec 7, 2011 at 3:42 PM, Brent Yorgey <[email protected]> wrote:
>
> > On Wed, Dec 07, 2011 at 11:34:28AM +0100, Giacomo Tesio wrote:
> > > Hi Haskellers,
> > >
> > > I'm wondering why, given that functions and referential transparency are
> > > first class citizens in haskell, it isn't possible to write a mapping
> > > function this way:
> > >
> > > f1 :: a -> b
> > >
> > > f2 :: a -> b
> > >
> > > f3 :: c -> a -> b
> > >
> > > map :: (a -> b) -> T a -> T b
> > > map f1 = anEquivalentOfF1InTCategory
> > > map f2 = anEquivalentOfF2InTCategory
> > > map f3 $ c = anEquivalentOfF3withCInTCategory
> > > map unknown = aGenericMapInTCategory
> > >
> > > Is it "just" the implementation complexity of the feature in ghc that
> > > prevents this?
> > > Or is it "conceptually" wrong?
> > >
> > > At a first look, I thought that most of complexity here should be related
> > > to function's equality, but than I thought that the function full name
> > > should uniquely map from the category of meanings in the programmer mind
> > to
> > > the category of implementations available to the compiler's.
> >
> > It is preciesly *because* of referential transparency that you cannot
> > do this. Suppose that
> >
> > f1 = \x -> bar x (5*x)
> >
> > then
> >
> > map (\x -> bar x (5*x))
> >
> > is supposed to be equivalent to 'map f1'. You might not think that is
> > too bad -- it is obvious that is the same as f1's definition. But
> > what about
> >
> > map (id (\z -> bar z (2*x + 3*x)))
> >
> > ? This is also required to be the same as 'map f1'. But now you have
> > to know about distributivity of multiplication over addition in order
> > to tell. This gets arbitrarily complicated (and, in fact,
> > undecidable) very quickly.
> >
> > -Brent
> >
> > _______________________________________________
> > 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
End of Beginners Digest, Vol 42, Issue 9
****************************************
