Extensible data types?

José Romildo Malaquias romildo@urano.iceb.ufop.br
Fri, 20 Oct 2000 07:21:51 -0200


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 = 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           = Left
      prj (Left x)  = Just x
      prj _         = Nothing

   instance SubType a b => SubType a (Either c b) where
      inj           = Right . inj
      prj (Right x) = prj x
      prj _         = 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é Romildo Malaquias <romildo@iceb.ufop.br>
Departamento de Computação
Universidade Federal de Ouro Preto