Natural numbers

A lot of common functions do recursion over the natural numbers. But Haskell does not have a Natural number type! Everyone uses Integer instead. This can lead to subtle bugs, because no-one considers the negative number case in their definitions. There were even examples of such bugs in the Prelude (take, drop) for about ten years.

So, let's add a Natural number type. Ideally, we should also restrict the interpretation of literal numeric patterns to values of Natural, so that any unintentional use of features belonging to other numeric types can be flagged as a static error.

Such a type could be presented as an optimized equivalent of an ordinary algebraic data type:

data Natural = Zero | Succ !Natural


fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

But what is the value of fib (-3)? A runtime stack overflow! Much better to catch this error at compile time.

See also NumericClasses.


If we do add them, then (a) they should probably be arbitrary in size; and (b) function definitions like fib should *not* be overloaded on Num, but should be monomorphic in Nat.


Not unreasonable at all, but restricting numeric patterns to Nat (actually, I'd say Natural if they're arbitrary in size) would likely break quite a bit of code, and I wonder if the payback in practice actually is worth it for Haskell'. Also, "-" and possibly other operations would presumably become partial, which might introduce new bugs. (Yes, could also return 0, but that could be a bit surprising as well.) Also, I don't think this has been widely implemented and tested yet, and thus it's hard to gauge the impact?


ticket: #79

Last modified 11 years ago Last modified on Mar 27, 2008 12:43:04 PM