title: S-expression Tree to Abstract Syntax Tree in OCaml
body: <p>I'm implementing a symbolic language in OCaml and have been struggling to translate my s-expression tree into an abstract syntax tree. </p>
  
  <p>The s-expression tree is </p>
  
  <pre><code>(* sexpr.mli *)
  type atom =
     | Atom_unit
     | Atom_int  of int
     | Atom_sym  of string
  
  type expr =
     | Expr_atom of atom
     | Expr_list of expr list
  </code></pre>
  
  <p>The abstract syntax tree is </p>
  
  <pre><code>(* ast.ml *)
  open Sexpr
  
  type sym = string
  
  (* abstract syntax tree nodes *)
  type expr =
     | Expr_unit
     | Expr_int    of int
     | Expr_sym    of sym
  
  (* Sexp.atom -&gt; Ast.expr *)
  let ast_of_atom a =
     match a with
        | Atom_unit  -&gt; Expr_unit
        | Atom_int n -&gt; Expr_int n
        | Atom_sym s -&gt; Expr_sym s
  
  (* Sexp.expr -&gt; Ast.expr *)
  let rec ast_of_sexpr sx = match sx with
      | Expr_atom a -&gt; ast_of_atom a
      | Expr_list l -&gt; 
      match l with
         | []   -&gt; ast_of_atom Atom_unit
         | [x]  -&gt; ast_of_sexpr x
         | h::t -&gt; ignore ( ast_of_sexpr h ); ast_of_sexpr ( Expr_list t )
  </code></pre>
  
  <p>The function <code>ast_of_sexpr</code> needs to conform with the type signature</p>
  
  <p><code>val ast_of_sexpr : Sexpr.expr -&gt; expr</code>. </p>
  
  <p><em>This is my challenge; I can't figure out a way, that conforms with the type signature, to recurse into the s-expression tree (i.e. nested lists) and translate s-expression tree nodes to abstract syntax tree nodes.</em> </p>
  
  <p>In an ideal world, I could evaluate the list head and recurse over the tail in one expression. I've tried to emulate this ideal using sequencing. But this, of course, ignores the left-side value and will only output the last value when printing a parsed stream of tokens. </p>
  
  <p>Can anyone suggest a method for evaluating the list head, <em>without ignoring the value</em>, and recursing deeper into the s-expression tree? I'm even open to reading better solutions for translating between the two trees.</p>