[Haskell-cafe] Natural Numbers: Best implementation?
Alexander Dunlap
alexander.dunlap at gmail.com
Thu Mar 12 23:01:57 EDT 2009
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
More information about the Haskell-Cafe
mailing list