[Haskell-cafe] Re: Shouldn't this loop indefinitely => take
(last [0..]) [0..]
john at repetae.net
Mon Apr 7 07:52:51 EDT 2008
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
data Num = Succ Num | Zero
not more efficient than strict types, which it very much is not. :)
John Meacham - ⑆repetae.net⑆john⑈
More information about the Haskell-Cafe