Re: [Haskell-cafe] Positive integers

On Friday 24 March 2006 23:29, Malcolm Wallace wrote:

Daniel McAllansmith 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