[Haskell-cafe] Equality of functions

[Jules Bean]

On 30 Nov 2004, at 13:22, Adam Zachary Wyner wrote:

> Question -- is this all there is to the issue, or is there something 
> more?
>  Apologies in advance for not understanding the math better here.
>

 From the point of view of a programmer, that's all there is to it: 
there is no way of proving two functions are the same except by 
exhaustively checking every input.

> Question -- though Haskell, as a lazy language, does not otherwise have
> problems with infinite lists, why does it here?

Try [1..]==[1..]
You'll find it runs forever. (Aside: [1..]==[2..] returns False 
straightaway, though)

In the same sense, you could try

(map f [1..]) == (map g [1..])

and it will return False quickly if they are different, but it will run 
forever if they are the same.

> Question -- is there some way around this problem?  It is very handy 
> to be
> able to have a variable over functions and then compare the value to a
> designated function.  This would let me say things like:
>

You don't need records to pair functions with strings, but yes, one way 
to do this is to make your functions more structured types and compare 
them some other way.

If you happen to know all your functions are 2nd order polynomials, 
then it suffices to check them at three points (or, check f, f', and 
f'' at 0, say): you could implement equality checks this way. In other 
function domains there may be other effective equality tests.

The general situation is: there is no effective way to check the 
equality of functions on infinite domains. However, for most particular 
classes of functions you would actually want to compare, there are 
specific effective procedures.

Jules