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