title: How to print a tree structure into a string fast in Ocaml?
body: <p>Assume I have a mathematical expression in a "tree" form in OCaml.  It's represented as an algebraic type like this:</p>
  
  <pre><code>type expr = 
     Number of int
    |Plus of expr*expr
  </code></pre>
  
  <p>Well, this is a <em>very</em> simplified definition, but it's enough to describe the problem.</p>
  
  <p>I want to convert it to a string in a reverse polish notation, so that <code>Plus (Number i, Number j)</code> becomes <code>(+ i j)</code>.  A straightforward implementation would be</p>
  
  <pre><code>let rec convert = function
     Number i -&gt; string_of_int i
    |Plus (a,b) -&gt; (let s = convert a in let p = convert b in "(+"^s^" "^p^")")
  </code></pre>
  
  <p>But the thing is that it's <strong>incredibly slow</strong> on some input (that have a big tree depth).  For example, this input works 5 seconds on my machine:</p>
  
  <pre><code>let rec make_pain so_far = function
    0 -&gt; so_far |i -&gt; make_pain (Plus (Number 1,so_far)) (i-1)
  
  let pain = make_pain (Number 1) 20000
  
  let converted = convert pain
  </code></pre>
  
  <p>It seems that string concatenation <code>x^y</code>, where <code>y</code> is a long string, is the performance problem.  Indeed, if I replace the <code>"(+"^s^" "^p^")"</code> expression with mere <code>s^p</code>, it becomes <strong>much</strong> faster.</p>
  
  <p>Using <code>printf</code> instead of concatenation doesn't make it any faster.  Converting to C might help, but isn't there an OCaml solution?</p>