[Haskell-beginners] Pattern matching over functions

[Ken KAWAMOTO]

Thanks Daniel and Felipe.

To me it seems Daniel's foo doesn't break referential transparency
because we can always replace "foo (+3) (\x -> x+3)" with "Yay :)",
and "foo (+3) somethingWhichIsTheSameButCan'tBeProvedToBe" with "Nay
:(".
It just contradicts our expectation that "foo (+3) something....ToBe"
should return "Yay :)", which is another story.

On Mon, Dec 12, 2011 at 3:24 AM, Daniel Fischer
<daniel.is.fischer at googlemail.com> wrote:
> 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.

This sounds like quite common function behavior as we can see in
  f n = if n > 0 then True else if n == 0 then f 0 else False
Here, f 1 returns True, f (-1) returns False, and f 0 doesn't
terminate. Still f is referentially transparent, isn't it?
If so, why can we not say foo is referentially transparent?

On the other hand, I agree that Felipe's obviouslyEqual is not
referentially transparent as its behavior really depends on how
Haskell runtime allocates functions (thunks) in memory.


I understand that we cannot construct such a function that always
terminates and decides functions' equality (equality defined as, say,
"f1 equals f2 iff f1 x == f2 x for any argument x").
But again, does this have something to do with referential transparency?
Isn't this just because it's undecidable problem?