Yeah I recently ran into this myself. (<a href="http://osdir.com/ml/haskell-cafe@haskell.org/2010-07/msg00020.html">http://osdir.com/ml/haskell-cafe@haskell.org/2010-07/msg00020.html</a>). It's not a bug, just a limitation of haskell's inference algorithm for mutually recursive groups of functions.<div>
<br></div><div>The problem is that haskell infers groups (the strongly connected components) of mutually recursive functions monomorphically. This means that all uses of the function in the group, and the definition, must all have the same type. In haskell 98, there was no way to get around this (not even with explicit type signatures), hence the rule that Russell pointed out in haskell 98 report: </div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">``If the programmer supplies explicit type signatures for more than one variable in a declaration group, the contexts of these signatures must be identical up to renaming of the type variables."</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">There was no meaningful way for this not be to be case with the old haskell 98 rules (since inferring such types was impossible).</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><br></span></div><div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">However,</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><br></span></div><div>Most implementations of haskell now have a (non Haskell 98 compliant) rule that breaks a function out of a mutually recursive group if it already has a type signature. Usually GHC requires the explicit enabling of extensions when functionality breaks with the haskell 98 standard, but in this case it lets you get away with it. However, GHC _does_ require the RelaxedPolyRec extension if you want to specify different contexts on your mutually recursive function group. </div>
<div><br></div><div>I imaging this is mostly just because allowing it without the extension would be contradicting an explicit rule in the haskell 98 standard. But there might be some monomorphism restriction like performance issues with it too, I'm not sure.</div>
<div><br></div><div><br></div><div>There has also been some work on alternative algorithms that solve this problem without the need for explicit type signatures. The mercury language supports full polymorphic recursion. And there is a paper on a better algorithm, that could potentially be used by haskell, here:</div>
<div><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.4930">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.4930</a></div><div><br></div><div>Phew, I think I got that all right, though I just learned this stuff myself only a month ago, so I'm mostly just passing it on :)</div>
<div>Hope that helps clear things up :)</div><div><br></div><div>- Job<br><br><div class="gmail_quote">On Fri, Jul 30, 2010 at 5:34 PM, <span dir="ltr"><<a href="mailto:roconnor@theorem.ca">roconnor@theorem.ca</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">I was one of the people on #haskell discussing this with Anupam.<br>
<br>
Note that that when you remove the signature of d, the result complies and ghci will state the inferred type of d is exactly the signature that you are not allowed to write.<br>
<br>
In my opinion, this is a bug in the Haskell 98 report where it says<br>
<br>
``If the programmer supplies explicit type signatures for more than one variable in a declaration group, the contexts of these signatures must be identical up to renaming of the type variables.<br>
<br>
The problem is that we cannot give a type signature to d with exactly the constraints of d_test because d doesn't have any type variable in its type signature.<br>
<br>
At the very least the Haskell report should allow type checking to proceed if everything in a declaration group has a signature even if the signatures don't have identical constraints.<br>
<br>
A trac ticket is needed for Haskell 2011, if one doesn't already exist.<div><div></div><div class="h5"><br>
<br>
On Sat, 31 Jul 2010, Anupam Jain wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
I am having trouble getting a small program to compile. The helpful folks at #haskell created a version of the<br>
program that does compile - <a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=28406#a28408" target="_blank">http://hpaste.org/fastcgi/hpaste.fcgi/view?id=28406#a28408</a> but it is not very clear<br>
to them (and to me) why the original program wouldn't type compile in the first place.<br>
<br>
Here's the program that refuses to compile -<br>
<br>
module Delme () where<br>
<br>
data DecisionState = A | B | C | D<br>
<br>
d_test :: Eq b => b -> b -> DecisionState -> DecisionState -> ()<br>
d_test test testVal trueState falseState =<br>
if (test == testVal)<br>
then d trueState<br>
else d falseState<br>
<br>
d :: DecisionState -> ()<br>
d A = d_test True True B C<br>
d B = d_test 1 2 C D<br>
d C = d_test True False A B<br>
d D = ()<br>
I get an error like -<br>
<br>
Delme.hs:13:0:<br>
Contexts differ in length<br>
(Use -XRelaxedPolyRec to allow this)<br>
When matching the contexts of the signatures for<br>
d_test :: forall b.<br>
(Eq b) =><br>
b -> b -> DecisionState -> DecisionState -> ()<br>
d :: DecisionState -> ()<br>
The signature contexts in a mutually recursive group should all be identical<br>
When generalising the type(s) for d_test, d<br>
<br>
Putting in the extension does get the program to type check but the original program should have type compiled<br>
in the first place.<br>
<br>
The ironic thing we discovered is that if we remove the type declaration for 'd', the program type checks, and<br>
GHC then derives the exact same type which we removed!<br>
<br>
Can some of the smarter people in the room please shed more light on this?<br>
<br>
-- Anupam<br>
<br>
<br>
<br>
</blockquote>
<br></div></div><font color="#888888">
-- <br>
Russell O'Connor <<a href="http://r6.ca/" target="_blank">http://r6.ca/</a>><br>
``All talk about `theft,''' the general counsel of the American Graphophone<br>
Company wrote, ``is the merest claptrap, for there exists no property in<br>
ideas musical, literary or artistic, except as defined by statute.''</font><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>