查找haskell中所有括号的组合？ [英] Find combinations of all brackets in haskell?

问题描述

我试图编写一个简单的代码来生成括号的所有组合。但是我坚持使用一个简单的类型错误。

  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]？

解决方案

>让我们定义平衡字符串是什么，归纳地说：

• 是平衡的
如果 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 我们打算连接结果吗？

相反，我们直接枚举所有无限均衡的字符串。
这是欧米茄 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 case

We 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 case

Let'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 <*> allParen

This 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中所有括号的组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！