Woops... scratch my stupitity... we could of course discover the test to be false on an extremely large integer. Bob -- God is real... Unless you define it as an integer. On 1 Dec 2004, at 01:19, Thomas Davie wrote:
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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe