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⑈