[Haskell-cafe] Equality of functions
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
>> 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