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

[Derek Elkins]

On Tue, 2007-12-18 at 23:04 -0800, Don Stewart wrote:
> jules:
> > 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.
> 
> 1) is always a challenge to particular types (heh) of people to do 2)

And indeed there are two distinct ways of enforcing balance in AVL trees
using the type system.  And of course, it would be "trivial" to do with
dependent types. Usually the problem isn't so much that it is not
possible, but that it is cumbersome and/or inefficient.

http://www.haskell.org/pipermail/haskell/2003-April/011621.html
http://www.haskell.org/pipermail/haskell/2003-April/011693.html

(random) Also that month, lambdabot 1.0!
http://www.haskell.org/pipermail/haskell/2003-April/011582.html