查找haskell中所有括號的組合？

Question

我想寫一個簡單的代碼來生成括號的所有組合。但我堅持一個簡單的類型錯誤。

balancedParens :: Int -> [String] 
balancedParens n 
      | n==0 = [] 
      | otherwise = placeParens 0 1 0 n [""] 
      where placeParens x lc rc n mlist 
           | lc == n = mlist 
           | rc == n = mlist 
           | lc < n = placeParens (x+1) (lc+1) rc n ((mlist !! x) ++ "L") 
           | rc < n = placeParens (x+1) lc (rc+1) n ((mlist !! x) ++ "R") 

有很多錯誤，但最突出的是

Couldn't match type ‘Char’ with ‘[Char]’ 
Expected type: [[Char]] 
    Actual type: [Char] 
In the first argument of ‘(!!)’, namely ‘mlist’ 
In the first argument of ‘(++)’, namely ‘(mlist !! x)’ 

失敗，模塊加載：無。

（（mlist !! x）++「L」）是一個列表，爲什麼類型錯誤？它如何匹配[Char]？

Answer 1

問題陳述

讓我們定義一個平衡串是什麼，電感：

• ""平衡
• 如果x和y是平衡的，"(" ++ x ++ ")" ++ y平衡

所有平衡字符串可以使用上述規則構建。

有限的情況下

我們要列舉正好具有n括號所有平衡的字符串。我們遵循上面的歸納規則。

paren :: Int -> [String] 
paren 0 = [""] 
paren n = [ "(" ++ x ++ ")" ++ y 
      | m <- [0..n-1] , x <- paren m , y <- paren (n-1-m) ] 

在第二個規則，我們把剩下的n-1括號兩個部分，在任何可能的方式。第一部分由m括號組成，0 <= m <= n-1。因此第二個 由(n-1)-m括號組成。

無限案例

讓我們來提高吧。我們不希望只有特定的組合n，我們希望包含所有這些組合。我們可能concat $ map paren [0..]但這感覺很愚蠢：爲什麼當我們打算連接結果呢時，爲什麼我們應該把這個集合劃分爲括號n？

而是讓我們直接枚舉所有無限均衡的字符串。 這是一個Omega monad的工作。我們只需要使用感應規則，再次聲明：

import Control.Monad.Omega 

allParen :: Omega String 
allParen = return "" 
     <|> (\x y -> "(" ++ x ++ ")" ++ y) <$> allParen <*> allParen 

這比paren更簡單，因爲我們永遠不需要算括號的數量。

快速測試在GHCI：

> take 20 $ runOmega allParen 
["","()","()()","(())","()()()","(())()","(()())","()(())","(())()()","(()())()","((()))","()()()()","(())(())","(()())()()","((()))()","(()()())","()(())()","(())()()()","(()())(())","((()))()()"]