Dmitry Vyal
On 10/19/2012 06:14 AM, AntC wrote:
Roman Cheplyaka
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 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
[snip] 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