[Haskell-beginners] Pattern matching over functions

[Daniel Fischer]

On Sunday 11 December 2011, 19:07:06, Graham Gill wrote:
> On 10-Dec-2011 11:17 AM, Ken KAWAMOTO wrote:
> > On Thu, Dec 8, 2011 at 3:14 PM, Brent Yorgey<byorgey at seas.upenn.edu>  
wrote:
> >> On Wed, Dec 07, 2011 at 06:10:01PM +0100, Giacomo Tesio wrote:
> >>> 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.
> > 
> > As I understand, this would be against lazy evaluation since it would
> > request to evaluate expressions in lambda, but I don't see how this
> > relates to referential transparency.
> > Can you elaborate this a little bit?
> 
> I second the question. From what I understand referential transparency
> means that an expression can be replaced by its value with no change to
> program semantics, or equivalently that a function always produces the
> same result/behaviour given the same input. How does determining whether
> two (pure) functions are equivalent break referential transparency?

I think if it were possible to find out whether two functions are the same 
for *every* pair of two functions, it wouldn't violate referential 
transparency.

But it's not possible, so all you have is that for some pairs of functions 
equality can be proved, for some pairs it can be disproved and for some 
pairs, it cannot be decided.

So

foo f g = if canProveEqual f g then "Yay :)" else "Nay :("

wouldn't be referentially transparent,

foo (+3) (\x -> x+3) = "Yay :)"
foo (+3) somethingWhichIsTheSameButCan'tBeProvedToBe = "Nay :("