[Haskell-cafe] Positive integers

[Daniel McAllansmith]

On Friday 24 March 2006 23:29, Malcolm Wallace wrote:
> Daniel McAllansmith <dagda at xtra.co.nz> 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