[Haskell-beginners] Pattern matching over functions

[Graham Gill]

Excellent, thanks Daniel and Felipe.

We don't even need to invoke infinite or undecidable problems, since 
it's easy to construct equal functions for which determining equality 
would be prohibitively expensive. If then you can only check equality 
for some functions, because you want compilation to finish, say, within 
the programmer's lifetime, you lose referential transparency.

Graham

On 11-Dec-2011 1:24 PM, Daniel Fischer wrote:
> 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 :("