title: Haskell - Convert De Bruijn terms to Lambda terms (and vice-versa)
body: <p>I have an assignment to write a Haskell program capable of converting De Bruijn terms to Lambda terms, and to convert Lambda terms into De Bruijn terms, and also to check if the terms are 'closed'.</p>
  
  <p>I am not looking for someone to do this assignment for me, but any assistance would be greatly appreciated! I am largely clueless about how to even get started with this.</p>
  
  <p>So, my biggest questions are: what's the difference between a De Bruijn term and a Lambda term?
  I understand what it means for a variable to be 'closed', but how could I check for that in Haskell?</p>
  
  <p>Any other assistance that you can think of would be greatly appreciated.</p>
  
  <p>Here is the full assignment:</p>
  
  <blockquote>
    <p>The (usual) lambda terms are defined as the data type:</p>
  
  <pre><code>data Term = Var Int | Lam Int Term | App Term Term deriving (Eq, Show, Read)
  </code></pre>
    
    <p>where variables are represented as integers. A term is called closed
    if for every <code>i</code> in <code>Var i</code> there's a term of the from <code>Lam i &lt;subterm&gt;</code> on
    the path from it to the root, providing it a binding.</p>
    
    <p>De Bruijn terms are defined as the data type:</p>
  
  <pre><code>data BTerm =BVar Int | BLam BTerm | BApp BTerm BTerm deriving (Eq,  Show, Read)
  </code></pre>
    
    <p>Write a Haskell function <code>db2lam</code> that transforms a de Bruijn term into
    a lambda term. Write a Haskell function <code>lam2db</code> that transforms a
    lambda term into a Bruijn term.</p>
    
    <p>Write a function <code>isClosed</code> that tests if a lambda term is closed. Write
    a function <code>isClosed</code> that tests if a de Bruijn term is closed.</p>
    
    <p>Chose one of the following two subjects:</p>
    
    <p>a) Implement normal order beta reduction for de Bruijn terms
    b) Implement normal order beta reduction for (the usual) lambda terms</p>
  </blockquote>
  
  <p>Thanks a lot for any assistance(Large or small)! I'm in the early stages of learning Haskell, so sorry for being so unsure! This assignment is way over my head at this time.</p>