<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Hi Michael,</p>
<p>I think you're making your own task harder than necessary. For
one thing, -XViewPatterns is nice, but in this case they hide some
of the structure. Most importantly, they hide that all the special
null-cases are actually unnecessary because the normal cases
already cover them. I would further advise to use layout to reveal
even more structure. That's especially useful when you later
convert the explicit recursion into a fold.</p>
<p>But even then, on a different level you're still working too
hard: You're parsing the string and building/correcting the tree
in one step. Why not create the tree, convert the tree, and then
read out the tree in three steps? It's still the same complexity
class but much easier to write and read. And once you are free to
think of the tree manipulations on their own it might help
recognize optimizations like those the solutions of other
commenters use.<br>
</p>
That's not to say your modifications are useless. But the
exploratory phase seems too early to apply them.<br>
<br>
Cheers,<br>
MarLinn<br>
<br>
<div class="moz-cite-prefix">On 2017-03-21 17:53, Michael Litchard
wrote:<br>
</div>
<blockquote
cite="mid:CAPYUwg_qCsqGKQJL8FU6iAyaKnOXCJ4_J37KCPCA_XSG8mcbCw@mail.gmail.com"
type="cite">
<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>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a>
Only members subscribed via the mailman list are allowed to post.</pre>
</blockquote>
<br>
</body>
</html>