On Sun, Apr 06, 2008 at 07:12:24AM -0700, John Meacham wrote:
On Fri, Apr 04, 2008 at 04:46:22PM +0100, Neil Mitchell wrote:
Where length xs = 1 and ys = 1000. This takes 1000 steps to tell the Int's aren't equal, since we don't have proper lazy naturals. If we did, it would take 2 steps.
Read this: http://citeseer.ist.psu.edu/45669.html - it argues the point I am trying to make, but much better.
I implemented this efficient lazy natural class once upon a time. it even has things like lazy multiplication:
I wonder about the efficiency of this implementation. It seems that for most uses the result is that the size of a Nat n is O(n), which means that in practice you probably can't use it for large numbers. e.g. it seems like last [1..n :: Nat] should use O(n) space, where last [1..n :: Integer] should take O(1) space. And I can't help but imagine that there must be scenarios where the memory use goes from O(N) to O(N^2), which seems pretty drastic. I imagine this is an inherent cost in the use of lazy numbers? Which is probably why they're not a reasonable default, since poor space use is often far more devastating then simple inefficiency. And of course it is also not always more efficient than strict numbers. -- David Roundy Department of Physics Oregon State University