haskell - 平衡语言，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扩展名(GHCi 中的 :set -XParallelListComp)，枚举除外。但这很容易解决，

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