gistfile1.hs

import Test.QuickCheck

data BracketStr = BracketStr [Bool] (Maybe (BracketStr, BracketStr))

lenBS :: BracketStr -> Int
lenBS (BracketStr s Nothing) = length s
lenBS (BracketStr s (Just (b1, b2))) = length s + lenBS b1 + lenBS b2 + 2

bs2str :: BracketStr -> String
bs2str (BracketStr s b) =
  let s' = map (\b -> if b then '1' else '0') s in
  case b of
    Nothing -> s'
    Just (b1, b2) -> s' ++ "(" ++ bs2str b1 ++ ")" ++ bs2str b2

instance Show BracketStr where
  show = bs2str

instance Arbitrary BracketStr where
  arbitrary = sized arbitrarySizedBStr

arbitrarySizedBStr :: Int -> Gen BracketStr
arbitrarySizedBStr n = do
  s <- resize (max 0 n) $ listOf arbitrary
  if length s > n - 2 then
    return $ BracketStr s Nothing
  else
    oneof [return $ BracketStr s Nothing, helper s (length s)]
  where
    helper s k = do
      b1 <- arbitrarySizedBStr (n - 2 - k)
      b2 <- arbitrarySizedBStr (n - 2 - k - (lenBS b1))
      return $ BracketStr s (Just (b1, b2))