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