[Haskell-beginners] Pattern matching over functions

[Brent Yorgey]

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