我试图编写一个简单的代码来生成括号的所有组合。但是我坚持使用一个简单的类型错误。
balancedParens :: Int - > [字符串] balancedParens n | n == 0 = [] |否则= 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）有很多错误，但最突出的是 $ b $ pre $ 无法将类型'Char'与' [Char]'预期类型：[[Char]] 实际类型：[Char] 在'（!!）'的第一个参数中，即'mlist'在'（++）'的第一个参数中，即'（mlist !! x）'
失败，模块加载：无。
（（mlist !! x）++L）是一个列表，为什么类型错误？问题陈述
如何与匹配[Char]？
解决方案 >让我们定义平衡字符串是什么，归纳地说：
所有平衡字符串可以使用上述规则构造。
有限情况我们想枚举所有平衡字符串正好 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 我们打算连接结果吗？
相反，我们直接枚举所有无限均衡的字符串。 这是欧米茄 monad。我们只需要再次使用归纳规则：
import Control.Monad.Omega allParen :: Omega String allParen = return< |> （\ x y - >（++ x ++）++ y）< $> allParen< *> allParen这比 paren 更简单我们从不需要计算括号中的数字。
GHCi的快速测试：
>取20美元runOmega allParen [，（），（）（），（（）），（）（）（），（（））（）， （（）（））， （）（（））， （（））（）（）， （（）（））（）， （（（）））， （）（）（）（） （（））（（））， （（）（））（）（）， （（（）））（），（（）（ ）（）） （）（（））（）， （（））（）（）（）， （（）（））（（）），（（（））） （）（）]
I am trying to write a simple code for generating all combinations of brackets..But am stuck with a simple type error.
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")There are lots of errors but most prominent is
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)’Failed, modules loaded: none.
((mlist !! x) ++ "L") is a list so why the type error? How come it is matching [Char]?
解决方案Problem statement
Let's define what a balanced string is, inductively:
- "" is balanced
- if x and y are balanced, "(" ++ x ++ ")" ++ y is balanced
All the balanced strings can be constructed using the above rules.
The finite caseWe want to enumerate all the balanced strings having exactly n parentheses. We follow the inductive rules above.
paren :: Int -> [String] paren 0 = [""] paren n = [ "(" ++ x ++ ")" ++ y | m <- [0..n-1] , x <- paren m , y <- paren (n-1-m) ]In the second rule, we divide the remaining n-1 parentheses in two parts, in any possible way. The first part is made of m parentheses, with 0 <= m <= n-1. The second therefore is made of (n-1)-m parentheses.
The infinite caseLet's raise the bar. We don't want just the combinations for a specific n, we want an exhaustive list comprising all of them. We might concat $ map paren [0..] but that feels silly: why should we partition the set over the number of parentheses n when we are going to concatenate the results anyway?
Instead, let's directly enumerate all the infinite balanced strings. This is a job for the Omega monad. We just need to use the inductive rules, once again:
import Control.Monad.Omega allParen :: Omega String allParen = return "" <|> (\x y -> "(" ++ x ++ ")" ++ y) <$> allParen <*> allParenThis is even simpler than paren since we never need to count the number of parentheses.
A quick test in GHCi:
> take 20 $ runOmega allParen ["","()","()()","(())","()()()","(())()","(()())","()(())","(())()()","(()())()","((()))","()()()()","(())(())","(()())()()","((()))()","(()()())","()(())()","(())()()()","(()())(())","((()))()()"]
更多推荐
查找haskell中所有括号的组合？
发布评论