Parens

Implementation



In [1]:

    
parensGen :: Int -> Int -> String -> [String]
parensGen 0 0 s = [ s ]
parensGen (-1) _ _ = []
parensGen _ (-1) _ = []
parensGen closedCount openCount suffix =
    parensGen (closedCount - 1) (openCount + 1) (')' : suffix) ++
    parensGen closedCount (openCount - 1) ('(' : suffix)



In [2]:

    
parensGen' :: Int -> Int -> String -> [String]
parensGen' 0 0 s = [ s ]
parensGen' (-1) _ _ = []
parensGen' _ (-1) _ = []
parensGen' openCount closedCount prefix =
    parensGen' (openCount - 1) (closedCount + 1) (prefix ++ "(") ++
    parensGen' openCount (closedCount - 1) (prefix ++ ")")



In [3]:

    
import Numeric.Natural



In [4]:

    
makeParens :: Natural -> [String]
makeParens x = parensGen (fromIntegral x) 0 ""

makeParens' :: Natural -> [String]
makeParens' x = parensGen' (fromIntegral x) 0 ""



In [5]:

    
makeParens 3
length $ makeParens 10









    





["((()))","(()())","()(())","(())()","()()()"]






    





16796

Tests

Invariants:

Combinations are valid
Combinations contain requested number of parens
There are no duplicate combinations
The number of combinations matches

Stack-based validator



In [6]:

    
validCombo :: String -> String -> Bool
validCombo "" "" = True
validCombo "" _ = False
validCombo (')':xs) ('(':ys) = validCombo xs ys
validCombo (x:xs) ys = validCombo xs (x:ys)



In [7]:

    
checkParens :: String -> Bool
checkParens xs = validCombo xs ""

Counter-based validator



In [8]:

    
validCombo' :: String -> Int -> Bool
validCombo' "" 0 = True
validCombo' _ (-1) = False
validCombo' ('(':xs) count = validCombo' xs (succ count)
validCombo' (')':xs) count = validCombo' xs (pred count)
validCombo' _ _ = False



In [9]:

    
checkParens' :: String -> Bool
checkParens' xs = validCombo' xs 0



In [10]:

    
checkParens' "(())"
checkParens' "(()))"
checkParens' "(2)"
checkParens' "("









    





True






    





False






    





False






    





False



In [11]:

    
import Test.QuickCheck



In [12]:

    
import Data.List

This test covers all but last invariant:



In [13]:

    
testValidCombos :: Natural -> Bool
testValidCombos n =
    let
        parens = makeParens n
    in
        all checkParens parens && 
        all ((== fromIntegral (2 * n)) . length) parens &&
        length parens == (length . nub) parens



In [14]:

    
quickCheckWith stdArgs { maxSize = 7 } testValidCombos









    





+++ OK, passed 100 tests.

Benchmarking



In [15]:

    
import System.TimeIt

Take note that both implementations are fully lazy, so properly benchmarking them is a bit of a challenge. For instance, in this example, only the first value is ever computed:



In [16]:

    
timeIt $ print $ head $ makeParens 14
timeIt $ print $ head $ makeParens' 14









    





"(((((((((((((())))))))))))))"
CPU time:   0.00s






    





"(((((((((((((())))))))))))))"
CPU time:   0.00s

Even this doesn't really help, because although the number of elements is determined, the elements themselves are not computed, which can lead to very surprising and misleading results:



In [17]:

    
timeIt $ print $ length $ makeParens 14
timeIt $ print $ length $ makeParens' 14









    





2674440
CPU time:  13.78s






    





2674440
CPU time:  13.27s

Here, no wonder, makeParens performs better than makeParens':



In [18]:

    
timeIt $ print $ length $ concat $ makeParens 14
timeIt $ print $ length $ concat $ makeParens' 14









    





74884320
CPU time:  15.00s






    





74884320
CPU time:  25.55s