[Haskell-beginners] Pattern matching over functions

[Brent Yorgey]

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 <byorgey at seas.upenn.edu> 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
> > 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