[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