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