<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: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.apple-style-span
        {mso-style-name:apple-style-span;}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page Section1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.Section1
        {page:Section1;}
-->
</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=Section1>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>You might find it helpful to read our new paper: Type checking
with open type functions&nbsp; http://research.microsoft.com/%7Esimonpj/papers/assoc-types/index.htm<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <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>Hugo Pacheco<br>
<b>Sent:</b> 07 April 2008 22:47<br>
<b>To:</b> Haskell Cafe<br>
<b>Subject:</b> [Haskell-cafe] Re: Type Families: infinite compile process?<o:p></o:p></span></p>

</div>

</div>

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

<p class=MsoNormal>The problem is that the representation probably does not
reduce to a normal form.<o:p></o:p></p>

<div>

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

</div>

<div>

<p class=MsoNormal>Say, for the case<o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal><span class=apple-style-span><i>type instance F (Nest a) x =
Either() (a,F a x)</i></span><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<div>

<p class=MsoNormal><span class=apple-style-span><i>fnn :: F (Nest a) (Nest a)</i></span><o:p></o:p></p>

</div>

<div>

<p class=MsoNormal><span class=apple-style-span><i>fnn = Left ()</i></span><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal>it compiles ok.<o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal>But why can't the representation be infinite, like any other
infinite data type?<o:p></o:p></p>

</div>

<div>

<p class=MsoNormal>Cheers,<o:p></o:p></p>

</div>

<div>

<p class=MsoNormal>hugo<o:p></o:p></p>

</div>

<div>

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

</div>

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

<div>

<p class=MsoNormal>On Mon, Apr 7, 2008 at 10:30 PM, Hugo Pacheco &lt;<a
href="mailto:hpacheco@gmail.com">hpacheco@gmail.com</a>&gt; wrote:<o:p></o:p></p>

<p class=MsoNormal>Hi guys,<o:p></o:p></p>

<div>

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

</div>

<div>

<p class=MsoNormal>I have been experimenting some weird stuff (risky, yes I
know) but the behaviour was certainly not the one I expected:<o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal><i>{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances
#-}</i><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal><i>module Nest where</i><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<div>

<p class=MsoNormal><i>data Nest a = Nil | Cons a (Nest (a,a))</i><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal><i>type family F a x :: *</i><o:p></o:p></p>

</div>

<div>

<div>

<p class=MsoNormal><i>type instance F (Nest a) x = Either () (a,F (Nest (a,a))
x)</i><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal><i>fnn :: F (Nest Int) (Nest Int)</i><o:p></o:p></p>

</div>

<div>

<p class=MsoNormal><i>fnn = Left ()</i><o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal>The following module fails to compile (or better,
compilation never ends).<o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal>Maybe there is something very bad going on due to the undecidable-instances
extension?<o:p></o:p></p>

</div>

<div>

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

</div>

<div>

<p class=MsoNormal>Any clue?<o:p></o:p></p>

</div>

<div>

<p class=MsoNormal>hugo<o:p></o:p></p>

</div>

</div>

</div>

</div>

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

</div>

</div>

</div>

</body>

</html>