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

[apfelmus]

Al Falloon wrote:
> OCaml has been getting a lot of mileage from its polymorphic variants
> (which allow structural subtyping on sum types) especially on problems
> relating to AST transformations and the infamous "expression problem".
> 
> Has there been any work on extending Haskell's type system with
> structural subtyping?

There's OO'Haskell but I don't know much about it. The problem with
subtyping is that it renders type inference undecidable and is more
limited than parametric polymorphism. It's more like a "syntactic
sugar", you can always explicitly pass around embeddings (a' -> a) and
projections (a -> Maybe a').

> What is the canonical solution to the expression problem in Haskell?
>
> What techniques do Haskellers use to simulate subtyping where it is
> appropriate?
> 
> I bring this up because I have been working on a Scheme compiler in
> Haskell for fun, and something like polymorphic variants would be quite
> convinent to allow you to specify versions of the AST (input ast, after
> closure conversion, after CPS transform, etc.), but allow you to write
> functions that work generically over all the ASTs (getting the free
> vars, pretty printing, etc.).

For this use case, there are some techniques available, mostly focussing
on traversing the AST and not so much on the different data
constructors. Functors, Monads and Applicative Functors are a structured
way to do that.

  S. Liang, P. Hudak, M.P. Jones. Monad Transformers and
  Modular Interpreters.
  http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html

  C. McBride, R. Paterson. Applicative Programming with Effects.
  http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf

  B. Bringert, A. Ranta. A Pattern for Almost Compositional Functions.
  http://www.cs.chalmers.se/~bringert/publ/composOp/composOp.pdf

The fundamental way is to compose your data types just like you compose
your functions. Here's an example

  data Expr a        = A (ArithExpr a) | C (Conditional a)
  data ArithExpr a   = Add a a | Mul a a
  data Conditional a = IfThenElse a a a | CaseOf a [(Int,a)]

  newtype Expression = E (Expr Expression)

Now, functions defined on (Conditional a) can be reused on Expressions,
although with some tedious embedding an projecting. I think that the
third paper mentioned above makes clever use of GADTs to solve this.

The topic of Generic programming is related to that and Applicative
Functors make a reappearance here (although not always explicitly
mentioned).

  http://haskell.org/haskellwiki/Research_papers/
  /Generics#Scrap_your_boilerplate.21


Regards,
apfelmus