<div dir="ltr"><div class="gmail-post-text">

<p>I'm prepping for a coding interview, and am examining the task of 
correcting unbalanced parentheses. The finger tree seems to be the right
 data structure.
As a proof of concept I've used <code>Data.Sequence</code> to test my idea. If this is the right direction to go, I'll write more specialized finger tree code.
The code works on the few test cases I have tried. Feedback appreciated.</p>

<pre class="gmail-lang-hs gmail-prettyprint gmail-prettyprinted"><code><span class="gmail-com">{-# LANGUAGE ViewPatterns #-}</span><span class="gmail-pln">
</span><span class="gmail-kwd">module</span><span class="gmail-pln"> Parenthesis </span><span class="gmail-kwd">where</span><span class="gmail-pln">
</span><span class="gmail-kwd">import</span><span class="gmail-pln"> BasicPrelude hiding </span><span class="gmail-pun">(</span><span class="gmail-pln">concat</span><span class="gmail-pun">,</span><span class="gmail-pln">null</span><span class="gmail-pun">,</span><span class="gmail-pln">empty</span><span class="gmail-pun">)</span><span class="gmail-pln">

</span><span class="gmail-kwd">import</span><span class="gmail-pln"> Data.Sequence hiding </span><span class="gmail-pun">(</span><span class="gmail-pln">length</span><span class="gmail-pun">)</span><span class="gmail-pln">
</span><span class="gmail-kwd">import</span><span class="gmail-pln"> Data.Foldable hiding </span><span class="gmail-pun">(</span><span class="gmail-pln">length</span><span class="gmail-pun">,</span><span class="gmail-pln">null</span><span class="gmail-pun">)</span><span class="gmail-pln">

balanceParens </span><span class="gmail-pun">::</span><span class="gmail-pln"> String </span><span class="gmail-pun">-></span><span class="gmail-pln"> String
balanceParens str </span><span class="gmail-pun">=</span><span class="gmail-pln"> go str </span><span class="gmail-pun">[]</span><span class="gmail-pln"> empty
  </span><span class="gmail-kwd">where</span><span class="gmail-pln">
    go </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">null </span><span class="gmail-pun">-></span><span class="gmail-pln"> True</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">=</span><span class="gmail-pln"> </span><span class="gmail-pun">[]</span><span class="gmail-pln">
    go </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">[]</span><span class="gmail-pln"> parens </span><span class="gmail-pun">=</span><span class="gmail-pln"> Data.Foldable.toList parens
    go </span><span class="gmail-pun">(</span><span class="gmail-str">'('</span><span class="gmail-pun">:</span><span class="gmail-pln">xs</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">null </span><span class="gmail-pun">-></span><span class="gmail-pln"> True</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">=</span><span class="gmail-pln"> go xs </span><span class="gmail-pun">[</span><span class="gmail-pln">RP</span><span class="gmail-pun">]</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">singleton </span><span class="gmail-str">'('</span><span class="gmail-pun">)</span><span class="gmail-pln">
    go </span><span class="gmail-pun">(</span><span class="gmail-str">')'</span><span class="gmail-pun">:</span><span class="gmail-pln">xs</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">null </span><span class="gmail-pun">-></span><span class="gmail-pln"> True</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">=</span><span class="gmail-pln"> go xs </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">fromList </span><span class="gmail-str">"()"</span><span class="gmail-pun">)</span><span class="gmail-pln">
    go </span><span class="gmail-pun">(</span><span class="gmail-str">'('</span><span class="gmail-pun">:</span><span class="gmail-pln">xs</span><span class="gmail-pun">)</span><span class="gmail-pln"> debit parens </span><span class="gmail-pun">=</span><span class="gmail-pln"> go xs </span><span class="gmail-pun">(</span><span class="gmail-pln">RP</span><span class="gmail-pun">:</span><span class="gmail-pln">debit</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">parens </span><span class="gmail-pun">|></span><span class="gmail-pln"> </span><span class="gmail-str">'('</span><span class="gmail-pun">)</span><span class="gmail-pln">
    go </span><span class="gmail-pun">(</span><span class="gmail-str">')'</span><span class="gmail-pun">:</span><span class="gmail-pln">xs</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">[]</span><span class="gmail-pln"> parens </span><span class="gmail-pun">=</span><span class="gmail-pln"> go xs </span><span class="gmail-pun">[]</span><span class="gmail-pln"> corrected
      </span><span class="gmail-kwd">where</span><span class="gmail-pln"> corrected </span><span class="gmail-pun">=</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-str">'('</span><span class="gmail-pln"> </span><span class="gmail-pun"><|</span><span class="gmail-pln"> parens</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">|></span><span class="gmail-pln"> </span><span class="gmail-str">')'</span><span class="gmail-pln">
    go </span><span class="gmail-pun">(</span><span class="gmail-str">')'</span><span class="gmail-pun">:</span><span class="gmail-pln">xs</span><span class="gmail-pun">)</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">RP</span><span class="gmail-pun">:</span><span class="gmail-pln">debit</span><span class="gmail-pun">)</span><span class="gmail-pln"> parens </span><span class="gmail-pun">=</span><span class="gmail-pln"> go xs debit </span><span class="gmail-pun">(</span><span class="gmail-pln">parens </span><span class="gmail-pun">|></span><span class="gmail-pln"> </span><span class="gmail-str">')'</span><span class="gmail-pun">)</span><span class="gmail-pln">
    go </span><span class="gmail-pun">(_:</span><span class="gmail-pln">xs</span><span class="gmail-pun">)</span><span class="gmail-pln"> debit parens </span><span class="gmail-pun">=</span><span class="gmail-pln"> go xs debit parens
    go </span><span class="gmail-pun">[]</span><span class="gmail-pln"> </span><span class="gmail-pun">(</span><span class="gmail-pln">RP</span><span class="gmail-pun">:</span><span class="gmail-pln">debit</span><span class="gmail-pun">)</span><span class="gmail-pln"> parens </span><span class="gmail-pun">=</span><span class="gmail-pln"> go </span><span class="gmail-pun">[]</span><span class="gmail-pln"> debit </span><span class="gmail-pun">(</span><span class="gmail-pln">parens </span><span class="gmail-pun">|></span><span class="gmail-pln"> </span><span class="gmail-str">')'</span><span class="gmail-pun">)</span></code></pre>

<p>example:</p>

<pre class="gmail-lang-hs gmail-prettyprint gmail-prettyprinted"><code><span class="gmail-pln">balanceParens </span><span class="gmail-str">"))("</span><span class="gmail-pln">
</span><span class="gmail-str">"(())()"</span><span class="gmail-pln">
balanceParens </span><span class="gmail-str">")))"</span><span class="gmail-pln">
</span><span class="gmail-str">"((()))"</span></code></pre>
    </div></div>