[Haskell-cafe] A yet another question about subtyping and heterogeneous collections
anthony_clayden at clear.net.nz
Mon Oct 22 23:50:24 CEST 2012
Dmitry Vyal <akamaus <at> gmail.com> writes:
> On 10/19/2012 06:14 AM, AntC wrote:
> > Roman Cheplyaka <roma <at> ro-che.info> writes:
> >>> 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
> > You might think there's only one 'chain' to get from (say) type A to type
> > 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
> > in other modules -- for all the compiler knows at that point.)
> > The modern way to handle this is using type functions (aka type families
> > associated types), but I'm not sure how that would apply here. (And, for
> > 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.
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
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
More information about the Haskell-Cafe