Type-Level arithmetic library
While cleaning up my home directory, I discovered some code I worked on a while ago which implements type level arithmetic. I have cleaned it up and decided to release. This library includes the following operations on type level naturals: addition subtraction multiplication division remainder GCD and also contains the following predicates test for zero test for equality < > <= >= This library uses a binary representation and can handle numbers at the order of 10^15 (at least). It also contains a test suite to help validate the somewhat unintuitive algorithms. You can retrieve this library with the following command darcs get --partial --tag '0.1' http://www.eecs.tufts.edu/~rdocki01/ typenats/ Enjoy, Rob Dockins PS Please let me know if you come up with useful ways to use this library! (I'm mostly just curious) Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
Robert Dockins wrote:
While cleaning up my home directory, I discovered some code I worked on a while ago which implements type level arithmetic.
I know for the usual Peano representation of natural numbers, at least, it's possible to represent addition and subtraction with a single class with two fundeps (because classes represent relations between types rather than functions on them). See <http://haskell.org/haskellwiki/Peano_numbers>.
On 2006-01-31, Ashley Yakeley <ashley@semantic.org> wrote:
Robert Dockins wrote:
While cleaning up my home directory, I discovered some code I worked on a while ago which implements type level arithmetic.
I know for the usual Peano representation of natural numbers, at least, it's possible to represent addition and subtraction with a single class with two fundeps (because classes represent relations between types rather than functions on them). See <http://haskell.org/haskellwiki/Peano_numbers>.
That's always seemed like such an ugly hack to me. If you use a digital representation, you can throw in at least one negative digit, and things just work. I really should write up and post my example of that using balanced base three on the wiki. -- Aaron Denney -><-
participants (3)
-
Aaron Denney -
Ashley Yakeley -
Robert Dockins