Subtyping

[Frank Atanassow]

Mansour Al-Mutairi wrote (on 18-08-01 17:29 +0000):
> I am a newbie but I think that what you are proposing can be simulated in 
> haskell. It is like subclassing in OOP. You can create a new type that is an 
> extension of the older one. Unlike OOP overloading, you will need to create 
> a new function that can work on the new type.
> 
> >data SomeObject = SomeInt Int | SomeString String | _
> 
> will become:
> 
> data SomeObject = SomeInt Int | SomeString String
> 
> >...later...
> >
> >data SomeObject |= SomeReal Double
> 
> will become:
> 
> data SomeObject2 = SO SomeObject | SomeReal Double

I want to point out that this approach runs into problems if the datatype
SomeObject is recursive. Consider a datatype of propositions:

  data Prop = TT | Or Prop Prop | Not Prop

Now you want to extend it:

  data Prop2 = Prop Prop | FF | And Prop2 Prop2

The problem is that you cannot form, e.g., the term:

  Or (And (Prop TT) (Prop TT)) FF

since Or wants Prop arguments, not Prop2 arguments like And.

You actually want the recursive instances of Prop in Prop's constructors'
types to be Prop2 now. This is a situation where the explicit fixpoint
datatype comes in handy:

  data Fix f = In (f (Fix f))

  data PropAlg p = TT | Or p p | Not p
  type Prop = Fix PropAlg

  data Prop2Alg p = Prop (PropAlg p) | FF | And p p
  type Prop2 = Fix Prop2Alg

Now you can write:

  p :: Prop2
  p = In (Prop (Or (In (And (In (Prop TT)) (In FF))) (In FF)))

which looks ugly, but is hidden if you are parsing input terms and
destructuring exclusively with folds.

I'm pretty sure that this technique can be taken much farther using type
classes to hide the Prop coercion, adding propositional variables and a
substitution monad, and perhaps doing normalization automatically with
customized folds and/or hiding the representation type with existentials, but
frankly I don't have the energy for that today.

BTW, this is not a beginner, or even intermediate, Haskell programmer's
technique. It will probably give you big headaches unless you are willing to
devote a few days to playing around with it. For example, if you really want
to take advantage of it you will need to learn how to go without
pattern-matching and how to write all your recursive algorithms
inductively... I think that's why no one really does this sort of thing in
Haskell in practice.

-- 
Frank Atanassow, Information & Computing Sciences, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-3261 Fax +31 (030) 251-379