Re: [Haskell-cafe] Positive integers
On Mar 26, 2006, at 4:35 PM, Daniel McAllansmith wrote: [Discussion of positive integers and Words] I was thinking about several things in this thread, torsors, overflow semantics, bounds checking... I wonder if there would be any merit in being able to define constrained subsets of integers and the semantics when/if they overflow. Oddly, I've just finished coding this up, with type-level bounds (represented by type-level ints). It's a big pile of modules on top of John Meacham's type-level Nats library, which add type-level Ints (as non-normalized Nat pairs), unknown endpoints (permitting Integer to fit in the same framework), and the actual bounded ints themselves. Naturally, I needed to define my own versions of the functionality in Eq, Ord, and Num. These resolve statically as much as possible (including some possibly dubious behavior with singleton intervals). That said, I don't try to do everything at the type level---it became too tiring, with not enough plausible benefit. Any and all: Drop me a line if you are interested, it's a stack of 3-4 modules and at best half-baked. I'd just gotten a mostly- complete version. -Jan-Willem Maessen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
For example, take UNIX nice levels -20 to 19. You could have
data ConstrainedInteger = CI {distToMax :: Natural, distToMin :: Natural}
this would ensure only the 40 integers can be represented.
Then you could have _something_ that defined what happened on overflow,
whether it wraps, reflects, errors, truncates or whatever.
Doesn't Ada have constrained number types which have similar behaviour?
--
burton samograd[EMAIL PROTECTED]
kruhft.blogspot.com www.myspace.com/kruhft metashell.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
Doesn't Ada have constrained number types which have similar behaviour? Yes. Just for comparison, the behaviour of the Ada number is to throw an exception at runtime if a number overflows its bounds. If these checks can be eliminated statically, then they are. If an operation will always give a runtime error then this is given as a warning at compile time. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
On Mon, 27 Mar 2006, Neil Mitchell wrote: Doesn't Ada have constrained number types which have similar behaviour? Yes. Just for comparison, the behaviour of the Ada number is to throw an exception at runtime if a number overflows its bounds. If these checks can be eliminated statically, then they are. If an operation will always give a runtime error then this is given as a warning at compile time. Quite similar to Modula (maybe also Pascal), as I indicated. There the bounded integers are called sub-ranges. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
On Friday 24 March 2006 23:29, Malcolm Wallace wrote:
Daniel McAllansmith [EMAIL PROTECTED] wrote:
Unless I've missed it, there is no typeclass for positive integers in
GHC. Is there any particular reason it doesn't exist?
Also, it seems Word would be a far better type in the likes of (!!),
length, etc. Is it just tradition that resulted in the use of Int?
There is a good argument that what you really want here is the lazy
infinite natural numbers. Think Peano:
data Natural = Zero | Succ Natural
The clear correspondance between lazy lists and the size/index of a lazy
list makes this type fairly compelling. It can be jolly useful,
particularly with infinite streams, to be able to compute
(length xs n)
without forcing the evaluation of the list to more than n places.
Of course, if the naturals were actually represented in Peano (unary)
form, that would be somewhat inefficient, but there are various
strategies that can be used to make the representation smaller whilst
retaining their nice properties.
I was thinking about several things in this thread, torsors, overflow
semantics, bounds checking...
I wonder if there would be any merit in being able to define constrained
subsets of integers and the semantics when/if they overflow.
For example, take UNIX nice levels -20 to 19. You could have
data ConstrainedInteger = CI {distToMax :: Natural, distToMin :: Natural}
this would ensure only the 40 integers can be represented.
Then you could have _something_ that defined what happened on overflow,
whether it wraps, reflects, errors, truncates or whatever.
When it comes to compile, or source preprocessing, time these numbers could be
realigned to a primitive Int or Word representation of suitable size and have
the appropriate overflow code written in. And, in the case of error or wrap
overflow semantics on a set of the right size, the overflow checks could be
disabled, like other assertions, at runtime.
Daniel
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
Daniel McAllansmith [EMAIL PROTECTED] wrote: Unless I've missed it, there is no typeclass for positive integers in GHC. Is there any particular reason it doesn't exist? Also, it seems Word would be a far better type in the likes of (!!), length, etc. Is it just tradition that resulted in the use of Int? There is a good argument that what you really want here is the lazy infinite natural numbers. Think Peano: data Natural = Zero | Succ Natural The clear correspondance between lazy lists and the size/index of a lazy list makes this type fairly compelling. It can be jolly useful, particularly with infinite streams, to be able to compute (length xs n) without forcing the evaluation of the list to more than n places. Of course, if the naturals were actually represented in Peano (unary) form, that would be somewhat inefficient, but there are various strategies that can be used to make the representation smaller whilst retaining their nice properties. Regards, Malcolm ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
On Fri, 24 Mar 2006, Malcolm Wallace wrote: Daniel McAllansmith [EMAIL PROTECTED] wrote: Unless I've missed it, there is no typeclass for positive integers in GHC. Is there any particular reason it doesn't exist? Also, it seems Word would be a far better type in the likes of (!!), length, etc. Is it just tradition that resulted in the use of Int? There is a good argument that what you really want here is the lazy infinite natural numbers. Think Peano: data Natural = Zero | Succ Natural The clear correspondance between lazy lists and the size/index of a lazy list makes this type fairly compelling. It can be jolly useful, particularly with infinite streams, to be able to compute (length xs n) without forcing the evaluation of the list to more than n places. Fortunately there are already List functions like genericLength and genericTake, which can handle such a number type. Shouldn't be Peano numbers part of the standard libraries? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Positive integers
Fortunately there are already List functions like genericLength and genericTake, which can handle such a number type. Shouldn't be Peano numbers part of the standard libraries? Natural numbers are being discussed as a possible part of the new Haskell' standard. http://hackage.haskell.org/trac/haskell-prime/ticket/79 Jared. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Positive integers
Unless I've missed it, there is no typeclass for positive integers in GHC. Is there any particular reason it doesn't exist? Also, it seems Word would be a far better type in the likes of (!!), length, etc. Is it just tradition that resulted in the use of Int? Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
