[Haskell-cafe] Equality of functions

[Thomas Davie]

On 1 Dec 2004, at 01:06, Bernard Pope wrote:

> On Tue, 2004-11-30 at 13:52 +0000, Jules Bean wrote:
>> 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.
>
> For some very generous definition of "quickly" :)

With respect to the fact that we do not know how fast f or g run, the 
only way to define quickly in this sense is relative to how fast f and 
g run.  We can return False from (map f [1..]) == (map g [1..]) with a 
constant time slow down from returning False from (f 1) == (g 1).  I'd 
call constant time reasonably 'quickly'.

Bob

--
What is the internet?
It's the largest equivalence class in the reflexive transitive 
symmetric closure of the relationship "can be reached by an IP packet 
from". -- Seth Breidbart