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

[Brad Larsen]

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)?

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?

> 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)?

Thanks!
Brad