[Haskell-cafe] Natural Numbers: Best implementation?

[Alexander Dunlap]

2009/3/12 Mark Spezzano <mark.spezzano at chariot.net.au>:
> 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