title: Applications of polymorphic recursion
body: <p>One limitation of implementing polymorphism in a language via monomorphisation (and monomorphisation only) is that you lose the ability to support polymorphic recursion (e.g. see rust-lang <a href="https://github.com/rust-lang/rust/issues/4287#issuecomment-11846582" rel="noreferrer">#4287</a>).</p>
  
  <p>What are some compelling use cases for supporting polymorphic recursion in a programming language? I have been trying to find libraries/concepts which use this and so far I've come across one example:</p>
  
  <ol>
  <li>In "The Naming Problem" where we'd like to have both (a) fast capture avoiding substitution and (b) fast alpha equivalence checking, there is the <a href="https://www.stackage.org/lts-11.15/package/bound-2.0.1" rel="noreferrer">bound</a> library (more detailed explanation <a href="https://www.schoolofhaskell.com/user/edwardk/bound" rel="noreferrer">here</a>). Both of these properties are desirable when writing a compiler for a functional programming language.</li>
  </ol>
  
  <p>To prevent the question from being overly broad, I'm looking for other programs/libraries/research papers that present applications of polymorphic recursion to traditional computer science problems such as those involved in writing compilers.</p>
  
  <p>Examples of things that I'm not looking for:</p>
  
  <ol>
  <li><p>Answers showing how you can encode X from category theory using polymorphic recursion, unless they demonstrate how encoding X can be beneficial for solving Y which falls under the criterion above.</p></li>
  <li><p>Small toy examples which show that you can do X with polymorphic recursion but you can't without it. </p></li>
  </ol>