<!DOCTYPE html><html><head><title></title><style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style></head><body><div>Thanks Richard and for the paper link! This answers my question and then some.<br></div><div><br></div><div>Cheers!</div><div><br></div><div>On Sun, Jun 7, 2020, at 6:53 PM, Richard Eisenberg wrote:<br></div><blockquote type="cite" id="qt" style="overflow-wrap:break-word;"><div>Yours is an example of polymorphic recursion, when a function calls itself at a different type than at which it was, itself, called. (What an ugly English construction. Apologies. But it's hard to describe this somehow.) Inference of polymorphic recursion is undecidable in the general case: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3091&rep=rep1&type=pdf" class="qt-">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3091&rep=rep1&type=pdf</a><br></div><div class="qt-"><br></div><div class="qt-">Some special cases can be inferred, and indeed GHC does a little inference of this in types, in some scenarios. (We'd actually prefer not to, in order to be consistent, but oddly it's hard to avoid in our algorithm.) But generally inferencers avoid trying here.<br></div><div class="qt-"><br></div><div class="qt-"><div>Richard<br></div><div><div><br></div><blockquote type="cite" class="qt-"><div class="qt-">On Jun 7, 2020, at 6:46 PM, chris done <<a href="mailto:haskell-cafe@chrisdone.com" class="qt-">haskell-cafe@chrisdone.com</a>> wrote:<br></div><div><br></div><div class="qt-"><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">I'm writing a type checker with type classes and for some reason thought<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">that the below program should be inferred and generalized automatically. I<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">wasn't sure whether or not GHC would actually accept this or not, so I had to test.<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">For both Hugs and GHC, a recursive definition's type is not generalized<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">by the inferer. You need a type signature. See below. I checked with<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">Hugs just in case there was a generalization limit in GHC due to its more exotic<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">capabilities (like how let generalization is disabled by type families).<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">I wonder: is it in general impossible or super hard to infer the most<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">general type for all cases like this without a type signature? Or is it just considered a <br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">rare case that we don't care about? Perhaps it has subtler downsides? <br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">It any case, I'm happy to just copy GHC and Hugs as it makes my life<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">easier to just require an explicit signature in this case.<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">Cheers<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- ERROR "Q.hs":4 - Type error in application<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- *** Expression : f (n - 1) 'a'<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- *** Term : 'a'<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- *** Type : Char<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- *** Does not match : ()<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- • Couldn't match expected type ‘()’ with actual type ‘Char’<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- • In the second argument of ‘f’, namely ‘'a'’<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- In the expression: f (n - 1) 'a'<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-"><br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">-- f :: Int -> a -> Int<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">f 0 x = 0<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">f 1 x = f 0 ()<br></div><div style="font-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;color:rgb(31, 31, 31);font-family:"Proxima Nova", system-ui, -apple-system, "Segoe UI", Arial, sans-serif;font-size:14px;font-variant-ligatures:normal;orphans:2;widows:2;background-color:rgb(255, 255, 255);" class="qt-">f n x = f (n-1) 'a'<br></div><div><span style="font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline !important;" class="qt-"><span class="font" style="font-family:Helvetica;"><span class="size" style="font-size:12px;">_______________________________________________</span></span></span><br></div><div><span style="font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline !important;" class="qt-"><span class="font" style="font-family:Helvetica;"><span class="size" style="font-size:12px;">Haskell-Cafe mailing list</span></span></span><br></div><div><span style="font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline !important;" class="qt-"><span class="font" style="font-family:Helvetica;"><span class="size" style="font-size:12px;">To (un)subscribe, modify options or view archives go to:</span></span></span><br></div><div><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-size-adjust:auto;-webkit-text-stroke-width:0px;" class="qt-">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br></div><div><span style="font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;-webkit-text-stroke-width:0px;text-decoration-line:none;text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline !important;" class="qt-"><span class="font" style="font-family:Helvetica;"><span class="size" style="font-size:12px;">Only members subscribed via the mailman list are allowed to post.</span></span></span><br></div></div></blockquote></div></div></blockquote><div><br></div></body></html>