Extensible data types?
S. Doaitse Swierstra
Fri, 20 Oct 2000 15:16:34 +0200
It is exactly for reasons like these that we developped our small
attribute grammar system:
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
>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 <firstname.lastname@example.org>
>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
PGP Public Key: http://www.cs.uu.nl/people/doaitse/
tel: +31 (30) 253 3962, fax: +31 (30) 2513791