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

[Al Falloon]

apfelmus wrote:
> 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').

I can see how nominal subtyping would make type inference a pain, but 
I'm pretty sure its solvable for structural subtyping because the 
inference algorithm can simply grow the type as it unifies the different 
terms. I think this paper describes how they pulled it off for OCaml:

http://citeseer.ist.psu.edu/garrigue02simple.html

Its true that subtyping can be considered syntactic sugar, but its the 
same sort of syntactic sugar as typeclasses, which are pretty popular.

In fact, the mapping you suggest is so close to the mapping of 
typeclasses that it suggests some sort of convenient subtyping library 
using typeclasses might be possible. Has anyone looked into this? Is 
that what Data.Typeable provides?

>> 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

Thank you, I will definitely look through those.