Re: [Haskell-beginners] Pattern matching over functions

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 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners