<div dir="ltr">Hi Michael,<div><br></div><div><div><div style="font-size:12.8px">Are there any strange constraints on the problem, such as the input string being 10s of GB long, or any particular correction strategy being required? Your code seems to add some parens to the start/end of the entire string to balance it, whereas I think I might have balanced "))(" to "()()()" given free reign. Is the goal efficiency or clarity or something else?</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">From personal taste, I would recommend including a suite of automated tests alongside your implementation even if it is not explicitly requested. A quickcheck test asserting that the output is always balanced and that the input string is a substring of the output might be appropriate.</div></div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 21 March 2017 at 16:53, Michael Litchard <span dir="ltr"><<a href="mailto:litchard.michael@gmail.com" target="_blank">litchard.michael@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="m_-7726037018957926027gmail-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="m_-7726037018957926027gmail-lang-hs m_-7726037018957926027gmail-prettyprint m_-7726037018957926027gmail-prettyprinted"><code><span class="m_-7726037018957926027gmail-com">{-# LANGUAGE ViewPatterns #-}</span><span class="m_-7726037018957926027gmail-pln">
</span><span class="m_-7726037018957926027gmail-kwd">module</span><span class="m_-7726037018957926027gmail-pln"> Parenthesis </span><span class="m_-7726037018957926027gmail-kwd">where</span><span class="m_-7726037018957926027gmail-pln">
</span><span class="m_-7726037018957926027gmail-kwd">import</span><span class="m_-7726037018957926027gmail-pln"> BasicPrelude hiding </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">concat</span><span class="m_-7726037018957926027gmail-pun">,</span><span class="m_-7726037018957926027gmail-pln">null</span><span class="m_-7726037018957926027gmail-pun">,</span><span class="m_-7726037018957926027gmail-pln">empty</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
</span><span class="m_-7726037018957926027gmail-kwd">import</span><span class="m_-7726037018957926027gmail-pln"> Data.Sequence hiding </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">length</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
</span><span class="m_-7726037018957926027gmail-kwd">import</span><span class="m_-7726037018957926027gmail-pln"> Data.Foldable hiding </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">length</span><span class="m_-7726037018957926027gmail-pun">,</span><span class="m_-7726037018957926027gmail-pln">null</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
balanceParens </span><span class="m_-7726037018957926027gmail-pun">::</span><span class="m_-7726037018957926027gmail-pln"> String </span><span class="m_-7726037018957926027gmail-pun">-></span><span class="m_-7726037018957926027gmail-pln"> String
balanceParens str </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go str </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> empty
</span><span class="m_-7726037018957926027gmail-kwd">where</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">null </span><span class="m_-7726037018957926027gmail-pun">-></span><span class="m_-7726037018957926027gmail-pln"> True</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> parens </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> Data.Foldable.toList parens
go </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-str">'('</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">xs</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">null </span><span class="m_-7726037018957926027gmail-pun">-></span><span class="m_-7726037018957926027gmail-pln"> True</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go xs </span><span class="m_-7726037018957926027gmail-pun">[</span><span class="m_-7726037018957926027gmail-pln">RP</span><span class="m_-7726037018957926027gmail-pun">]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">singleton </span><span class="m_-7726037018957926027gmail-str">'('</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-str">')'</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">xs</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">null </span><span class="m_-7726037018957926027gmail-pun">-></span><span class="m_-7726037018957926027gmail-pln"> True</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go xs </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">fromList </span><span class="m_-7726037018957926027gmail-str">"()"</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-str">'('</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">xs</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> debit parens </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go xs </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">RP</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">debit</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">parens </span><span class="m_-7726037018957926027gmail-pun">|></span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-str">'('</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-str">')'</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">xs</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> parens </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go xs </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> corrected
</span><span class="m_-7726037018957926027gmail-kwd">where</span><span class="m_-7726037018957926027gmail-pln"> corrected </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-str">'('</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun"><|</span><span class="m_-7726037018957926027gmail-pln"> parens</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">|></span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-str">')'</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-str">')'</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">xs</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">RP</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">debit</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> parens </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go xs debit </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">parens </span><span class="m_-7726037018957926027gmail-pun">|></span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-str">')'</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln">
go </span><span class="m_-7726037018957926027gmail-pun">(_:</span><span class="m_-7726037018957926027gmail-pln">xs</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> debit parens </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go xs debit parens
go </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">RP</span><span class="m_-7726037018957926027gmail-pun">:</span><span class="m_-7726037018957926027gmail-pln">debit</span><span class="m_-7726037018957926027gmail-pun">)</span><span class="m_-7726037018957926027gmail-pln"> parens </span><span class="m_-7726037018957926027gmail-pun">=</span><span class="m_-7726037018957926027gmail-pln"> go </span><span class="m_-7726037018957926027gmail-pun">[]</span><span class="m_-7726037018957926027gmail-pln"> debit </span><span class="m_-7726037018957926027gmail-pun">(</span><span class="m_-7726037018957926027gmail-pln">parens </span><span class="m_-7726037018957926027gmail-pun">|></span><span class="m_-7726037018957926027gmail-pln"> </span><span class="m_-7726037018957926027gmail-str">')'</span><span class="m_-7726037018957926027gmail-pun">)</span></code></pre>
<p>example:</p>
<pre class="m_-7726037018957926027gmail-lang-hs m_-7726037018957926027gmail-prettyprint m_-7726037018957926027gmail-prettyprinted"><code><span class="m_-7726037018957926027gmail-pln">balanceParens </span><span class="m_-7726037018957926027gmail-str">"))("</span><span class="m_-7726037018957926027gmail-pln">
</span><span class="m_-7726037018957926027gmail-str">"(())()"</span><span class="m_-7726037018957926027gmail-pln">
balanceParens </span><span class="m_-7726037018957926027gmail-str">")))"</span><span class="m_-7726037018957926027gmail-pln">
</span><span class="m_-7726037018957926027gmail-str">"((()))"</span></code></pre>
</div></div>
<br>______________________________<wbr>_________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/haskell-<wbr>cafe</a><br>
Only members subscribed via the mailman list are allowed to post.<br></blockquote></div><br></div>