[Haskell-cafe] Has anyone looked into adding subtyping to Haskell?

[Al Falloon]

Mark T.B. Carroll wrote:
> I don't know what the infamous "expression problem" is, nor am I
> familiar with polymorphic variants or structural subtyping, but have you
> looked at the Data.Generics.* stuff and Scrap Your Boilerplate papers?
> They may be relevant.
>   
The expression problem is "a new name for an old problem", basically 
being able to extend a data type and functions over the data type in 
seperate modules with no knowledge of each other. Here is a link to (I 
think) the original description:

http://www.daimi.au.dk/~madst/tool/papers/expression.txt

Structural subtyping is something like "duck typing" in dynamic 
languages, but checked at compile time. For records, it means that if 
you only access two labels then the function will work on any record 
that has those labels with those types, even if it may have more labels. 
For variants (or sum-types, or tagged unions, or whatever they are 
called in Haskell) it means that if your function can handle certain 
cases, then it can also handle values that range over less cases. So in 
pseudo-Haskell with imaginary subtyping:

data Vertical a = U a | D a
data Horizontal a = L a | R a
data Direction a = #Vertical a | #Horizontal a  -- borrowing ocaml 
syntax: this means that Direction shares constructors with Vertical and 
Horizontal

getData :: Direction a -> a
getData (U a) = a
getData (D a) = a
getData (L a) = a
getData (R a) = a

getLeftStick :: IO (Vertical Int)
getRightStick :: IO (Horizontal Int)

main = do { accel <- getLeftStick; print (getData accel) }

So getData doesn't care that accel is Horizontal and not Direction 
because Horizontal is a sub-type of direction. Of course, in this syntax 
since you named the subtyping relationship its more technically nominal 
subtyping (like in traditional static OO languages) not structural 
subtyping (which figures out the subtype relationship from the structure 
automatically, so if we just reused the U,D,L, and R constructors in 
Direction).

I have looked into SYB briefly. I will probably end up using it to keep 
the amount of code to a minimum, but it won't save me from having to 
define a different data type for each version of the AST if I want to 
preserve type safety.