4
\$\begingroup\$

Write a function (in Haskell) which makes a list of strings representing all of the ways you can balance N pairs of parentheses:

Example:

balancedParens 0
[""]
balancedParens 1
["()"]
balancedParens 2
["()()","(())"]
balancedParens 3
["()()()","(())()","()(())","(()())","((()))"]

My code produces the right answer but is very slow.

I would appreciate any help on how to speed it up (I have little Haskell experience, so the main struggle for me was implementing the proper algorithm).

module Balanced.Parens where

import Data.List
import Data.List.Split

mutateBP :: String -> [String]
mutateBP "()" = ["(())", "()()"]
mutateBP  xs  = [xs ++ "()", "()" ++ xs, "(" ++ xs ++ ")"]

continuousSubSeqs :: String -> [String]
continuousSubSeqs = filter (not . null) . concatMap inits . tails

indicesOfSubStr :: String -> String -> [Int]
indicesOfSubStr []  _   = []
indicesOfSubStr sub str = filter (\i -> sub `isPrefixOf` drop i str) $ head sub `elemIndices` str

splitBP :: String -> String -> [[String]]
splitBP s xs = chunksOf 2 (concat (map (\i -> [take (i + 1) xs, drop (i + 1) xs]) (indicesOfSubStr s xs)))

get1st :: (a,b,c) -> a
get1st (a,_,_) = a

get2st :: (a,b,c) -> b
get2st (_,b,_) = b

get3st :: (a,b,c) -> c
get3st (_,_,c) = c

zipWithNums' :: String -> [(Char, Int, Int)]
zipWithNums' xs = zip3 xs (parensNum xs) [0..]

findMatch "" = (0, "", "", 0)
findMatch xs = (length xs, group, tail', matchIdx)
  where zipWithNums = zip3 xs (parensNum xs) [0..]
        matchNum = 1 + (get2st $ head zipWithNums)
        matchPar = if '(' == (get1st . head) zipWithNums then ')' else '('
        matchAndTail = dropWhile (\x -> (get1st x /= matchPar) || (get2st x /= matchNum) ) (tail zipWithNums)
        matchIdx = if 0 == length matchAndTail then 0 else (get3st $ head matchAndTail) + 1
        group = take matchIdx xs
        tail' = drop matchIdx xs

groups xs = nub $ filter (\x -> (length $ get2st x) /= 0) [(take (xs_l - l) xs, g, t) | (l, g, t, idx) <- map findMatch (tails xs)]
  where xs_l = length xs

parensNum :: String -> [Int]
parensNum xs = scanl (\acc x -> if '(' == x then acc + 1 else acc - 1) 1 xs

isValidBP :: String -> Bool
isValidBP "" = True
isValidBP xs = (length valid_parens_num) - 1 == length xs
  where parens_num = parensNum xs
        valid_parens_num = takeWhile (>0) parens_num

balancedParens :: Int -> [String]
balancedParens 0 = [""]
balancedParens 1 = ["()"]
balancedParens n = nub $ concat $ map (\x -> [p ++ z ++ s| p <- [get1st x], z <- mutateBP $ get2st x, s <- [get3st x]]) gr
  where gr = concat $ map groups (balancedParens (n - 1))
\$\endgroup\$
5
\$\begingroup\$

The code can be sped up, and it can also be simplified. For n > 0, there is a unique way to write a balanced string as (a)b where a and b are balanced strings.

a and b must have n-1 pairs of parentheses, total. This leads us to the following solution:

balancedParens 0 = [""]
balancedParens n = ["(" ++ a ++ ")" ++ b | i <- [0 .. n - 1], a <- balancedParens i, b <- balancedParens (n - i - 1)]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Great answer! Thanks! I need to sleep on it to fully understand the idea. I feel really stupid right now :-) \$\endgroup\$ – Eralde Jan 13 '15 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.