# All balanced parentheses for a given N

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))


## 1 Answer

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)]

• Great answer! Thanks! I need to sleep on it to fully understand the idea. I feel really stupid right now :-) – Eralde Jan 13 '15 at 0:00