[Haskell-cafe] Natural Numbers: Best implementation?

Mark Spezzano mark.spezzano at chariot.net.au
Thu Mar 12 22:54:39 EDT 2009



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.




Mark Spezzano


No virus found in this outgoing message.
Checked by AVG. 
Version: 7.5.557 / Virus Database: 270.11.12/1998 - Release Date: 12/03/2009
6:23 PM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090313/696d19b7/attachment.htm

More information about the Haskell-Cafe mailing list