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

[Jules Bean]

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.

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