<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
 /* Font Definitions */
 @font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.EmailStyle17
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page WordSection1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
        {page:WordSection1;}
-->
</style>
<!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1" />
 </o:shapelayout></xml><![endif]-->
</head>

<body lang=EN-GB link=blue vlink=purple>

<div class=WordSection1>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>I don&#8217;t know an algorithm that can always infer the most general
types in situations like this.&nbsp; In your example, if you give a signature
for the simple function (f :: Y Maybe -&gt; Int), and use RelaxedPolyRec, then
GHC will happily infer the type you want for g.&nbsp;&nbsp; For RelaxedPolyRec
to work its magic, you just need to cut the strongly connected component with a
type signature &#8211; but you can cut it anywhere you please.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Interesting example, though. &nbsp;I&#8217;ve added a test to
GHC&#8217;s regression suite to make sure we do infer the right type for g,
given the monomoprhic type for f.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Simon<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<div style='border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt'>

<div>

<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>

<p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:
"Tahoma","sans-serif"'>From:</span></b><span lang=EN-US style='font-size:10.0pt;
font-family:"Tahoma","sans-serif"'> haskell-cafe-bounces@haskell.org
[mailto:haskell-cafe-bounces@haskell.org] <b>On Behalf Of </b>Job Vranish<br>
<b>Sent:</b> 22 June 2010 16:06<br>
<b>To:</b> Haskell Cafe mailing list<br>
<b>Subject:</b> [Haskell-cafe] Inferring the most general type<o:p></o:p></span></p>

</div>

</div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal>Esteemed fellow haskellers,<br>
<br>
I recently ran into a very simple real life case where Haskell's rules for
inferring the types for mutually recursive definitions resulted in a type that
was less general than it could be. It took me a while to realize that the type
error I was getting wasn't actually a problem with my code. I understand why
Haskell does this (it infers the strongly connected mutually recursive
definitions monomorphically), but I think it _could_ infer the more general
type even with recursive definitions like this.<br>
<br>
Here is a simplified example that illustrates the problem:<br>
<br>
&gt; import Data.Maybe<br>
<br>
&gt; -- The fixed point datatype<br>
&gt; data Y f = Y (f (Y f))<br>
<br>
&gt; -- silly dummy function<br>
&gt; maybeToInt :: Maybe a -&gt; Int<br>
&gt; maybeToInt = length . maybeToList<br>
<br>
&gt; -- f :: Y Maybe -&gt; Int<br>
&gt; f (Y x) = g maybeToInt x<br>
<br>
&gt; g h x = h $ fmap f x<br>
<br>
This is the type it wants to infer for g<br>
g :: (Maybe Int -&gt; Int) -&gt; Maybe (Y Maybe) -&gt; Int<br>
<br>
This is the type I think it should have, note you can't force the type with a
typesig without -XRelaxedPolyRec<br>
g :: (Functor f) =&gt; (f Int -&gt; b) -&gt; f (Y Maybe) -&gt; b<br>
<br>
If I use -XRelaxedPolyRec I can manually specify the more general type, but
then I have to convince myself that there isn't a more general type that I'm
missing.<br>
<br>
<br>
Are there other known algorithms that yield a more general type? and if so,
what was the rational for Haskell keeping the current method?<br>
<br>
I worked out an alternative algorithm that would give a more general type
(perhaps the most general type) but it has factorial complexity and probably
wouldn't be good for strongly connected groups with 7 or more members.<br>
<br>
Even so, I would much rather have the inferred types always be the most general
ones and be required to add type signatures for mutually recursive groups with
7 or more members (which probably need to be redesigned anyway) than be always
required to manually figure out the more general signatures. <br>
What do you think?<br>
<br>
<br>
- Job<o:p></o:p></p>

</div>

</div>

</body>

</html>