在 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
["","()","()()","(())","()()()","(())()","(()())","()(())","(())()()","(()())()","((()))","()()()()","(())(())","(()())()()","((()))()","(()()())","()(())()","(())()()()","(()())(())","((()))()()"]

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

Find combinations of all brackets in haskell?

haskell

types

问题陈述

有限情况

无限的情况