[Haskell-cafe] Re: Shouldn't this loop indefinitely => take (last [0..]) [0..]

[David Roundy]

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