Jules Bean jules at jellybean.co.uk
Tue Nov 30 08:52:41 EST 2004

```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

```