haskell-cafe@haskell.org
[Top] [All Lists]

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

Subject: Re: [Haskell-cafe] Creating a type for a subset of the integers
From: Jules Bean
Date: Wed, 19 Dec 2007 07:00:53 +0000
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@xxxxxxxxxxx
http://www.haskell.org/mailman/listinfo/haskell-cafe

<Prev in Thread] Current Thread [Next in Thread>