[Haskell-cafe] Creating a type for a subset of the integers

[Jules Bean]

Brad Larsen wrote:
> On Wed, 19 Dec 2007 02:00:53 -0500, Jules Bean <jules at jellybean.co.uk> 
> wrote:
> 
>> Brad Larsen wrote:
>>> Hi there list,
>>>  How would one go about creating a new type for a subset of the 
>>> integers, for (contrived) example just the even integers?  I was 
>>> thinking of making a new type
>>>  newtype EvenInt = EvenInt Integer
>>>  but the problem with this is that it accepts any integer, even odd 
>>> ones.  So to prevent this, the module does not export the constructor 
>>> for it---rather, the module exports a function `mkEvenInt' that 
>>> creates an EvenInt if the given value is acceptable or raises an 
>>> error otherwise.
>>>   What's the right way to do this?  Thanks!
>>
>> There are two ways:
>>
>> (1) Have a representation which admits invalid values, and provide 
>> combinators which only perfect validity, and prove that consumers 
>> using your combinators can't produce invalid values.
>>
>> (2) Have a cleverly designed representation such that every 
>> representation is valid.
>>
>> An example here, for (2) would be to store n/2; there is a bijection 
>> between 'Integer' and 'EvenInt' given by n/2.
> 
> To make sure I understand, an example of (1) would be to export only a 
> ``smart constructor'' that somehow converts invalid values to valid ones 
> (say, add 1 to arguments that are odd)?

I just meant one that throws a runtime error if they are not.

> In your example of 2, how would you go about storing n/2?  Store just n 
> as in (newtype EvenInt = EvenInt Integer) and then write all functions 
> that deal with EvenInts so that they account for the division by two?

You would store n/2. So "8" would be represented as EvenInt 4, "14" as 
EvenInt 7. Then you write the num instance to account for the division. 
Check out the num instance in Data.Fixed for an example.

> 
>> In real, more complex problems, (2) often isn't possible and we resort 
>> to (1). E.g. the representation of balanced trees (AVL? RedBlack?) 
>> admits invalid values (both unbalanced trees and out-of-order trees) 
>> and   we rely on the reduced set of combinators never to generate one.
>>
>> Jules
> 
> In my particular case, or what I actually want to do, is define a finite 
> segment of the integers (0-42, say) as a new type and have that checked 
> at compile time.  Any way of doing this w/o defining Peano numbers or a 
> whole bunch of nullary constructors (i.e. I'm hoping to be able to 
> define a type whose constructor will accept only Integer arguments 
> between 0 and 42)?

Not at compile-time, no. The best you can do is runtime error.

There is no compile-time facility to check that an Int lies in a 
particular range. Consider, for example, that the int might not be known 
at compiletime:

do
   id <- myThreadID
   return (MkSmallInt id)

^^ how can the compiler know?

In general, of course, the question of calculating if an int is under 42 
at compile time is the question of partial evaluation. Partial 
evaluation at compile time is flat-out impossible for IO actions, and 
although it's possible for pure functions, GHC doesn't do it to any 
significant extent. (It would make the compiler potentially 
non-terminating, of course!)

Jules