[Haskell-cafe] Re: Shouldn't this loop indefinitely => take (last
[0..]) [0..]
David Roundy
droundy at darcs.net
Mon Apr 7 07:45:31 EDT 2008
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
More information about the Haskell-Cafe
mailing list