Instance chains

[garyb]

This is the only thing left from the type system wishlist that doesn't have it's own issue.

• The paper: http://homepages.inf.ed.ac.uk/jmorri14/pubs/morris-icfp2010-instances.pdf
• Some interesting discussions on the GHC Trac: https://ghc.haskell.org/trac/ghc/ticket/9334

[garyb]

I was thinking named instances might help us out when it comes to instance chains. In the original paper I think they have to be defined in a closed setting as the chain is syntactically specified together, but we could perhaps do something with the names so that they are extensible, so the chain (or maybe, graph I guess) can be extended by other libraries. Although I guess we'd need to be careful in what we allow there to prevent inference from behaving differently in the presence of different combinations of libraries.

Having just had a quick read of the GHC discussion, there's an interesting point too that may be worth considering: perhaps a restricted form of this can be allowed when overlapping instances are declared together in the same module, by essentially making the order of definitions in that module the chain - and allow the overlaps without warning, as the behaviour can be considered well specified (assuming we make the type checker actually use the ordering). If overlapping instances occur across module boundaries then the warning reappears. This does have the problem of only allowing closed setups for things like Inject, but I wonder if it would be easier / a half way fix to get us some amount of the benefit of instance chains without making things too complex.

Just some thoughts I had knocking around anyway.

[paf31]

Thanks for writing this one up. I'm not sure how instance chains will interact with functional dependencies, but I am interested to see if they can solve some problems for us.

[LiamGoodacre]

I am currently prototyping the instance groups part of this. Not doing the backtracking/guards bit.
I'll open a PR soon for discussion.

[toraritte]

(The original link above for the paper is dead, and its new home is at J Garrett Morris' page: https://jgbm.github.io/pubs/morris-icfp2010-instances.pdf . His PhD dissertation, Type Classes and Instance Chains, is also related.)