[Haskell-cafe] RFE: Extensible algebraic user-defined data types?

[Benjamin Franksen]

On Thursday 28 April 2005 16:48, Dimitry Golubovsky wrote:
> Is it possible to have such a feature in the future versions of the
> Haskell language?
>
> For example, there is an Either datatype which is Left a| Right b.
>
> Suppose I want to extend this datatype to the one including
> possibility of neither Left or Right (i. e. None).
> [...] 
>
> data NEither a b = <Either a b> | None
>
> where datatype in angles is a parent datatype, and all its possible
> data constructors are included, and their list is extended with None.
>
> which gave me possibilities: Left a | Right b | None

Surely NEitehr must be a different type than Either, since it allows the 
constructor None, whereas Either does not. But then we have two different 
types with overlapping constructor names. That means the type of

	Right "x"

can no longer be infered: it could be one of {NEither String a, Either String 
a}, but which?

Thus, in order to have such a feature, you have to drop complete type 
inference and instead allow subtyping. This has been studied to some extent, 
for instance in http://www.cs.chalmers.se/~nordland/ohaskell/ especially 
http://www.cs.chalmers.se/~nordland/ohaskell/survey.html#sect5

Unfortunately, O'Haskell is no longer being maintained, nor (or so it seems) 
is its successor Timber (http://www.cse.ogi.edu/pacsoft/projects/Timber/).

> Probably I wouldn't expect to be able to reuse Nothing here (although
> I might want to) because Nothing already has been defined to be of the
> type Maybe.
>
> This is just a suggestion, that's why it is posted in the Cafe.
>
> PS Or is there a similar feature in the language already?

Not one I know of.

> Regarding reusing constructor names across several datatypes: is it
> possible to qualify them with their enclosing datatype name, like
> Maybe.Nothing where there is a name conflict? Then I might reuse
> Nothing in my hypothetical data type, and it would be NEither.Nothing
> if conflicting with Maybe.Nothing

The problem is that you would either need to do this sort of qualification for 
all terms (i.e. loose type inference completely), or else loose the property 
that the inference engine always inferes the most general type. See the above 
link (the second one) for a detailed (but quite readable) discussion.

Cheers,
Ben