[Haskell-cafe] Equality of functions

Thomas Davie tom.davie at gmail.com
Tue Nov 30 20:19:44 EST 2004

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'.


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

More information about the Haskell-Cafe mailing list