Extensible data types?

S. Doaitse Swierstra doaitse@cs.uu.nl
Fri, 20 Oct 2000 15:16:34 +0200

It is exactly for reasons like these that we developped our small 
attribute grammar system:


Doaitse Swiesrtra

At 7:21 AM -0200 10/20/00, Jos=E9 Romildo Malaquias wrote:
>I am back with the issue of extensible union types. Basically
>I want to extend a data type with new value constructors.
>Some members of the list pointed me to the paper
>    "Monad Transformers and Modular Interpreters"
>    Sheng Liang, Paul Hudak and Mark Jones
>The authors suggest using a type constructor to express
>the disjoint union of two other types:
>    data Either a b =3D Left a | Right b
>which indeed is part of the Haskell 98 Prelude. Then they introduce
>a subtype relationship using multiparameter type classes:
>    class SubType sub sup where
>       inj :: sub -> sup			-- injection
>       prj :: sup -> Maybe sub		-- projection
>The Either data type consructor is then used to express
>the desired subtype relationshipe:
>    instance SubType a (Either a b) where
>       inj           =3D Left
>       prj (Left x)  =3D Just x
>       prj _         =3D Nothing
>    instance SubType a b =3D> SubType a (Either c b) where
>       inj           =3D Right . inj
>       prj (Right x) =3D prj x
>       prj _         =3D Nothing
>The authors implemented their system in Gofer, due to
>restrictions in the type class system of Haskell.
>But now that there are Haskell extensions to support
>multiparametric type classes, that could be implemented
>in Haskell.
>The above code fails to type check due to instances
>overlapping. Hugs gives the following error message:
>    ERROR "SubType.hs" (line 10): Overlapping instances for class "SubType"
>    *** This instance   : SubType a (Either b c)
>    *** Overlaps with   : SubType a (Either a b)
>    *** Common instance : SubType a (Either a b)
>(I did not check Gofer, but is there a way to solve these
>overlapping of instances in it?)
>So this is scheme is not going to work with Haskell (extended
>with multiparameter type classes).
>I would like hear any comments from the Haskell comunity on
>this subject. Is there a workaround for the overlapping instances?
>Prof. Jos=E9 Romildo Malaquias <romildo@iceb.ufop.br>
>Departamento de Computa=E7=E3o
>Universidade Federal de Ouro Preto
>Haskell mailing list

S. Doaitse Swierstra, Department of Computer Science, Utrecht University
                       P.O.Box 80.089, 3508 TB UTRECHT,   the Netherlands
                       Mail:  mailto:doaitse@cs.uu.nl
                       WWW:   http://www.cs.uu.nl/
                       PGP Public Key: http://www.cs.uu.nl/people/doaitse/
                       tel:   +31 (30) 253 3962, fax: +31 (30) 2513791