[Haskell-cafe] Creating a type for a subset of the integers
Brad Larsen
brad.larsen at gmail.com
Thu Dec 20 10:55:12 EST 2007
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
More information about the Haskell-Cafe
mailing list