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

[John Meacham]

On Mon, Apr 07, 2008 at 04:45:31AM -0700, David Roundy wrote:
> 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.

Oh, yes. I certainly wouldn't recommend them as some sort of default,
they were sort of a fun project and might come in handy some day.

By efficient, I meant more efficient than the standard lazy number
formulation of

data Num = Succ Num | Zero 

not more efficient than strict types, which it very much is not. :)

        John


-- 
John Meacham - ⑆repetae.net⑆john⑈