Re: [Haskell-cafe] Natural Numbers: Best implementation?
Am Samstag, 14. März 2009 23:33 schrieben Sie: On Fri, 13 Mar 2009, Wolfgang Jeltsch wrote: Class instances should satisfy certain laws. (Although these laws are often not stated explicitely, they are assumed to hold by users of the class and they should hold to make the instance sensible.) In the case of Num, I would expect num + negate num to equal num. equal zero ? Exactly. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
On Fri, 13 Mar 2009, Mark Spezzano wrote: 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 This option looks like non-negative package. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
On Fri, 13 Mar 2009, Wolfgang Jeltsch wrote: Am Freitag, 13. März 2009 09:21 schrieb Roman Cheplyaka: * Alexander Dunlap alexander.dun...@gmail.com [2009-03-12 20:01:57-0700] Also, a lot of functions just take Integers so it would be more of a pain to use. AFAIK there are very few fuctions that take Integers. Many functions take instances of Integral, but it's not a problem to make your own type such an instance. I’d say that it is a problem. Class instances should satisfy certain laws. (Although these laws are often not stated explicitely, they are assumed to hold by users of the class and they should hold to make the instance sensible.) In the case of Num, I would expect num + negate num to equal num. equal zero ? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
Hi Mark, On Mar 13, 2009, at 3:54 AM, Mark Spezzano wrote: I was wondering what the best way to implement Natural number would be. Is there a package which already does this? there are two packages on Hackage that implement natural numbers using algebraic datatypes: 'numbers' has a module Data.Number.Natural that implements them in unary notation (zero and successor), 'nat' has Data.Number.Nat that uses a binary encoding. Cheers, Sebastian___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
* Alexander Dunlap alexander.dun...@gmail.com [2009-03-12 20:01:57-0700] Also, a lot of functions just take Integers so it would be more of a pain to use. AFAIK there are very few fuctions that take Integers. Many functions take instances of Integral, but it's not a problem to make your own type such an instance. -- Roman I. Cheplyaka :: http://ro-che.info/ Don't let school get in the way of your education. - Mark Twain ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
Am Freitag, 13. März 2009 04:01 schrieb Alexander Dunlap: 2. Use the type data Natural = Zero | Succ !Natural […] 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. Not only that but also because operations like addition now take at least linear time. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
Am Freitag, 13. März 2009 04:53 schrieb Brandon S. Allbery KF8NH: On 2009 Mar 12, at 22:54, Mark Spezzano wrote: I was wondering what the best way to implement Natural number would be. Is there a package which already does this? type-level on Hackage. I think, the original poster wanted value-level naturals, not type-level naturals. 2. Use the type data Natural = Zero | Succ !Natural One of the reasons people use type-level naturals is to get laziness; you've made this strict. Is there a reason? Do you really mean type-level naturals? The following is a definition of value-level naturals: data Natural = Zero | Succ Natural Type-level naturals would be defined like this: data Zero data Succ nat Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
Am Freitag, 13. März 2009 09:21 schrieb Roman Cheplyaka: * Alexander Dunlap alexander.dun...@gmail.com [2009-03-12 20:01:57-0700] Also, a lot of functions just take Integers so it would be more of a pain to use. AFAIK there are very few fuctions that take Integers. Many functions take instances of Integral, but it's not a problem to make your own type such an instance. I’d say that it is a problem. Class instances should satisfy certain laws. (Although these laws are often not stated explicitely, they are assumed to hold by users of the class and they should hold to make the instance sensible.) In the case of Num, I would expect num + negate num to equal num. This wouldn’t hold for a Natural instance of Num. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
On 2009 Mar 13, at 4:25, Wolfgang Jeltsch wrote: Am Freitag, 13. März 2009 04:53 schrieb Brandon S. Allbery KF8NH: On 2009 Mar 12, at 22:54, Mark Spezzano wrote: I was wondering what the best way to implement Natural number would be. Is there a package which already does this? type-level on Hackage. I think, the original poster wanted value-level naturals, not type- level naturals. My (possibly incorrect) understanding was that value-level naturals required runtime range checks, whereas type-level naturals allowed you to validate them at compile time. I thought I'd mentioned that in my response, contrasting type-level naturals with value-level newtypes and other implementations. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Natural Numbers: Best implementation?
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 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
2009/3/12 Mark Spezzano mark.spezz...@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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Natural Numbers: Best implementation?
On 2009 Mar 12, at 22:54, Mark Spezzano wrote: I was wondering what the best way to implement Natural number would be. Is there a package which already does this? type-level on Hackage. 2. Use the type data Natural = Zero | Succ !Natural One of the reasons people use type-level naturals is to get laziness; you've made this strict. Is there a reason? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
