generateParens.hs

import Control.Monad

generateParens :: Int -> [String]
generateParens n = generateParens' n ""

generateParens' :: Int -> String -> [String]
generateParens' n xs
  | n == o = [xs ++ replicate u ')']
  | u == 0 = generateParens' n (xs ++ "(")
  | otherwise = [xs ++ "(", xs ++ ")"] >>= generateParens' n
  where o = length $ filter (=='(') xs       -- open parens
        u = o - (length $ filter (==')') xs) -- unmatched parens
        

gistfile1.txt

*Main> generateParens 3
["((()))","(()())","(())()","()(())","()()()"]