平衡语言,2个非终端符号,列表理解

Question

所以,我正在读一本书,"形式语言理论导论",它描述了一种语言L(G) = {a^n ++ b^n | n > 0}.

它有以下产品:

S -> ab | aSb

因此会产生以下语言:

a, ab, aabb, aaabbb, ...

我想知道如何使用Haskell的列表理解来创建这种语言.我知道我可以使用字符串进行列表理解,但我几乎是初学者,并且不确定如何获得像我想要的这些字符串的无限列表.

我想象的是:

[ x ++ y | x <- ["a","aa",..] y <- ["b","bb",..]] 

Answer 1

根据生产规则,

S -> ab | aSb

我们可以写

s = ["ab"] ++ [ "a" ++ x ++ "b" | x <- s ]

以便

~> take 5 s
["ab","aabb","aaabbb","aaaabbbb","aaaaabbbbb"]
it :: [[Char]]

您的尝试可以使用小编辑,

[ x ++ y | x <- ["a","aa",..] | y <- ["b","bb",..]]

所以它使用Parallel List Comprehensions扩展(:set -XParallelListComp在GHCi中),枚举除外.但这很容易解决,

[ x ++ y | x <- [replicate n 'a' | n <- [1..]] 
         | y <- [replicate n 'b' | n <- [1..]]]