在haskell中找到所有括号的组合？

Question

我正在尝试编写一个简单的代码来生成所有括号组合。但是我遇到了一个简单的类型错误。

\n\n

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

\n\n

错误有很多，但最突出的是

\n\n

Couldn\'t match type \xe2\x80\x98Char\xe2\x80\x99 with \xe2\x80\x98[Char]\xe2\x80\x99\nExpected type: [[Char]]\n  Actual type: [Char]\nIn the first argument of \xe2\x80\x98(!!)\xe2\x80\x99, namely \xe2\x80\x98mlist\xe2\x80\x99\nIn the first argument of \xe2\x80\x98(++)\xe2\x80\x99, namely \xe2\x80\x98(mlist !! x)\xe2\x80\x99\n

\n\n

失败，已加载模块：无。

\n\n

((mlist !! x) ++ "L") 是一个列表，为什么类型错误？怎么会匹配到[Char]呢？

\n

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

相反，让我们直接枚举所有无限平衡字符串。这是欧米茄单子的工作。我们只需要再次使用归纳规则：

import Control.Monad.Omega

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

paren这比我们永远不需要计算括号的数量还要简单。

GHCi 中的快速测试：

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