[Haskell-cafe] Creating a type for a subset of the integers
Don Stewart
dons at galois.com
Wed Dec 19 02:04:28 EST 2007
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)
We've a page on the wiki about this idiom,
http://www.haskell.org/haskellwiki/Smart_constructors
including links to type level enforcement.
Last time I tried type level decimals they were still a little bit
hairy. This might be easier now with type families though.
-- Don
More information about the Haskell-Cafe
mailing list