[Haskell-cafe] Code Review Request - Unbalanced Parenthesis correction

[David Turner]

It can't be done in better than O(n) time as you have to look at the whole
input.

I think you must be using O(n) space too. Consider a string of the form
"()()()()...()())": You know the output starts with a '(' but you cannot
know the second character of the output until you have read all the way to
the end of the string and found the final character is unmatched.

On 21 Mar 2017 18:04, "Michael Litchard" <litchard.michael at gmail.com> wrote:

> David,
>
> Am I mistaken in believing the code I have in both O(1) in time and space?
> I'm certain that my use of Data.Sequence, and therefore finger trees, has
> this code at O(1) time.
> Doesn't using a lazy list mean I am using O(1) space? Or, would I have to
> use the conduits or pipes library?
>
> On Tue, Mar 21, 2017 at 10:52 AM, David Turner <
> dct25-561bs at mythic-beasts.com> wrote:
>
>> ... or it could be a ploy to see how you deal with incomplete or vague
>> specs; how you ask clarifying questions etc.
>>
>> Adding sufficiently many opening parens at the start can't obviously be
>> done without traversing the whole input first, whereas adding them as you
>> discover excesses of closing parens is possible to implement in a streaming
>> fashion, i.e. with O(1) memory usage and only traversing the input once.
>>
>> On 21 Mar 2017 17:44, "Michael Litchard" <litchard.michael at gmail.com>
>> wrote:
>>
>> I got this idea from looking at glassdoor comments of previous
>> interviewees. The spec was vague, but I imagined that the requirement would
>> need to be efficient and keep contiguous parenthesis unaltered.
>> so
>> balanceParens ")))" == "()()()" would be incorrect.
>>
>>
>>
>> On Tue, Mar 21, 2017 at 10:20 AM, David Turner <
>> dct25-561bs at mythic-beasts.com> wrote:
>>
>>> My attempt to replicate the OP's strategy but not impl:
>>>
>>> balanceParens :: String -> String
>>> balanceParens s =  replicate neededOpening '('
>>>            ++ s ++ replicate neededClosing ')'
>>>   where
>>>   depthChange '(' = 1
>>>   depthChange ')' = -1
>>>   depthChange _   = 0
>>>
>>>   depths = scanl (+) 0 $ map depthChange s
>>>   neededOpening = negate $ minimum depths
>>>   neededClosing =          last    depths + neededOpening
>>>
>>>
>>>
>>> On 21 March 2017 at 17:16, David McBride <toad3k at gmail.com> wrote:
>>>
>>>> Whether your algorithm is correct depends on how you are supposed to
>>>> rebalance them.  My naive attempt gives very different results.
>>>>
>>>> bal :: String -> String
>>>> bal = go 0
>>>>   where
>>>>     go :: Int -> String -> String
>>>>     go 0 "" = ""
>>>>     go n "" = replicate n ')'
>>>>     go n ('(':xs) = '(' : (go (n + 1) xs)
>>>>     go 0 (')':xs) = '(' : ')' : (go 0 xs)
>>>>     go n (')':xs) = ')' : (go (n - 1) xs)
>>>>
>>>> bal "))("
>>>> "()()()"
>>>>
>>>> bal ")))"
>>>> "()()()"
>>>>
>>>> On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
>>>> <litchard.michael at gmail.com> wrote:
>>>> > 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 Data.Sequence 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.
>>>> >
>>>> > {-# LANGUAGE ViewPatterns #-}
>>>> > module Parenthesis where
>>>> > import BasicPrelude hiding (concat,null,empty)
>>>> >
>>>> > import Data.Sequence hiding (length)
>>>> > import Data.Foldable hiding (length,null)
>>>> >
>>>> > balanceParens :: String -> String
>>>> > balanceParens str = go str [] empty
>>>> >   where
>>>> >     go [] [] (null -> True) = []
>>>> >     go [] [] parens = Data.Foldable.toList parens
>>>> >     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>>>> >     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>>>> >     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>>>> >     go (')':xs) [] parens = go xs [] corrected
>>>> >       where corrected = ('(' <| parens) |> ')'
>>>> >     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>>>> >     go (_:xs) debit parens = go xs debit parens
>>>> >     go [] (RP:debit) parens = go [] debit (parens |> ')')
>>>> >
>>>> > example:
>>>> >
>>>> > balanceParens "))("
>>>> > "(())()"
>>>> > balanceParens ")))"
>>>> > "((()))"
>>>> >
>>>> >
>>>> > _______________________________________________
>>>> > Haskell-Cafe mailing list
>>>> > To (un)subscribe, modify options or view archives go to:
>>>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>>> > Only members subscribed via the mailman list are allowed to post.
>>>> _______________________________________________
>>>> Haskell-Cafe mailing list
>>>> To (un)subscribe, modify options or view archives go to:
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>>> Only members subscribed via the mailman list are allowed to post.
>>>>
>>>
>>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170321/793d7ee6/attachment.html>