Leaving Haskell behind
This part is interesting:<p><i>A good concrete example here is a compiler project I was involved in where our first implementation had AST nodes which used a type parameter to represent their expression types: in effect, this made it impossible to produce a syntax tree with a type error, because if we attempted this, our compiler itself wouldn&#x27;t compile. This approach did catch a few bugs as we were first writing the compiler! It also made many optimization passes into labyrinthine messes whenever they didn&#x27;t strictly adhere to the typing discipline that we wanted: masses of casts and lots of work attempting to appease the compiler for what should have been simple rewrites. In that project, we eventually removed the type parameter from the AST</i><p>which also seems to conflict with this:<p><i>Using data structures indexed by compiler phase is a good example of a “fancy type-level feature” that I&#x27;ve found remarkably useful in the past.</i><p>Both of these sound like the &quot;AST typing problem&quot; - <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37114976">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37114976</a><p>which I admit I&#x27;m a bit skeptical of, because the problem is type safety, and not the compiler&#x27;s actual algorithm or actual performance.<p>But I guess the first one is for syntax trees, and the &quot;trees that grow&quot; paper (linked in the article) is for back end passes?  Does that change the problem so much?<p>I&#x27;m not experienced with back end passes for compilers, but I personally don&#x27;t see the problem of using either a Map&lt;AST, ExtraInfo&gt; or a nullable field.<p>I just hacked on a toy codebase that had the Expr&lt;void&gt; and Expr&lt;T&gt; type safe solution, and it&#x27;s interesting.  But my first impression is that it causes more allocations and makes the code a bit longer.<p>---<p>I guess another way to justify the Map is that it&#x27;s like math -- a &quot;typing relation&quot; is an association from expr to type, so a map or multi-map seems natural to model it.