[Haskell-cafe] A yet another question about subtyping and heterogeneous collections

[AntC]

Dmitry Vyal <akamaus <at> gmail.com> writes:

> 
> On 10/19/2012 06:14 AM, AntC wrote:
> > Roman Cheplyaka <roma <at> ro-che.info> writes:
> >
[snip]
> >>> instance (Upcast a b, Upcast b c) => Upcast a c where
> >>>    upcast = (upcast :: b -> a) . (upcast :: c -> b)
> >> This is the offending instance. Remember, GHC only looks at the instance
> >> head ("Upcast a c" here) when it decides which instance to use.
> >>
> >> Roman
> >>
> > Hi Dmitry, looks like you've got the classic (show . read) difficulty. In
> > your "Upcast a c" instance, the compiler is trying to figure out the type 
of b.
> >
> > You might think there's only one 'chain' to get from (say) type A to type 
D --
> > that is via Upcast A B to Upcast B C to Upcast C D; but there's also an
> > instance Upcast x x -- which means there could be any number of Upcast A A,
> > Upcast B B, etc links in the chain.
> >
> > (And this doesn't count all the other possible instances that might be 
defined
> > in other modules -- for all the compiler knows at that point.)
> >
> > The modern way to handle this is using type functions (aka type families 
aka
> > associated types), but I'm not sure how that would apply here. (And, for 
the
> > record, the old-fashioned way would use functional dependencies, as per the
> > Heterogenous Collections paper aka 'HList's).
> >
> > AntC
> >
> 
> Hello Antony,
> do I understand you correctly, that the error message is the result of 
> compiler using depth first search of some kind when calculating 
> instances?  Also can you please elaborate a bit more on using functional 
> dependencies for this problem? Upcast x y is not a function, it's a 
> relation, y can be upcasted to different x'es and different y's can be 
> upcasted to single x.
> 
> Dmitry
> 

Hi Dmitry, you've specified UndecidableInstances (which means you're 
saying "trust me, I know what I'm doing"). So the compiler isn't trying 
to 'calculate' instances so much as follow your logic, and the error mesage 
means that it can't follow. I'm guessing that the stack overflow is because 
it's tryng to search, and getting into a loop of Upcast x x ==> Upcast x x 
==> ... Increasing the stack size is not likely to help.

You could try removing the Upcast x x instance to see what happens and 
understand it better. (But I can see this won't help with solving the bigger 
problem.) 

The more usual approach for heterogeneous collections (for example in HList, 
or somewhat differently in lenses) is to define a class 'Has x r' (record r 
has field x), with methods get/set. Define instances for all your 'base' 
collection types and their fields. Then define an instance for the subtype to 
inherit from the supertype.

But that does require a strict hierarchy of sub-/super-types, so your wish to 
upcast in any direction won't fit.

For your general question on functional dependencies, you'll need to read the 
wiki's. Relations and functions are isomorphic (and that's what fundeps takes 
advantage of); but it needs careful structuring of the instances to make type 
inference tractable.

HTH
AntC