2009/3/12 Mark Spezzano :

Hi,

I was wondering what the best way to implement Natural number would be. Is there a package which already does this?

Here are some options:

1.  Don’t bother. Just use Integer.

2.  Use the type

data Natural = Zero | Succ !Natural

3.  Use the following definition taken from the Gentle Introduction to Haskell 98

newtype Natural = MakeNatural Integer

toNatural ::Integer-> Integer

toNatural x | x < 0 = error “Can’t create negative naturals!”

             | otherwise = MakeNatural x

fromNatural :: Natural -> Integer

fromNatural (MakeNatural i) = i

and then...

instance Num Natural where

  fromInteger = toNAtural

  x + y       = toNatural (fromNatural x + fromNatural y)

  x – y       = etc..

  x * y       = etc...

Which method is best? So far, I’ve been picking option #1 – just leaving things as they are and using Integer to keep things simple.

I’ve got that feeling that [2] would be fast and [3] would be slow. Comment appreciated on the merits of each.

Cheers,

Mark Spezzano

I would tend to use option (1) unless there's a compelling reason not to. Since naturals aren't closed under subtraction, you would in practice probably have just as many non-total functions as you would with the regular Int{,eger} type. Also, a lot of functions just take Integers so it would be more of a pain to use. In terms of speed, I think that [3] would be reasonably fast (unless you do a ton of subtraction with bounds-checking) and [2] would probably be quite slow, because you don't get the speed-boost from doing computations right on the processor. Alex