通过列表理解和递归理解列表的无限列表

Question

我正在从命令式（主要是 C）编程角度学习 Haskell，并对 Prolog 有一些基本的了解。在尝试解决一些练习时，我遇到了一个困扰我一段时间的练习。找到答案后，更多的疑问出现了。我必须生成一个无限的列表列表，从作为输入给出的字母表开始（也称为 kleene 闭包）。该函数定义如下：

kleene :: [a] -> [[a]]
kleene xs = []:[kle++[x] | kle <- kleene xs, x <- xs]

它有效，但我似乎不明白它是如何工作的（我认为这是练习的要点）。根据我对列表理解的理解，我获取第一个列表的第一个元素（此处kleene xs），然后遍历第二个列表的元素（xs）。此示例显示了 kleene 闭包的前 20 个元素。

> take 20 $ kleene [1,2,3]
> [[],[1],[2],[3],[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3],[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1]]

现在，这是怎么回事？为什么对此的评价没有失控？是否是因为惰性评估，如果不需要的话，可以继续进行而无需真正计算？如果我尝试替换并计算表达式，我就会陷入循环：

[[],[kleene [1,2,3],1],[kleene [1,2,3],2],[kleene [1,2,3],3],[kleene [1,2,3],...]

为了计算 kleene，我必须无限地计算它。在第一行，一旦我解决了 kleene 我得到

[[],[[],kleene [1,2,3],1,1],[[], kleene [1,2,3],1,2],[[], kleene [1,2,3],1,3],...]

但这样它就应该永远持续下去。为什么我得到的输出逐渐变大，而不是无限大的元素？是不是因为惰性求值，每次递归调用都算作链表的一个元素，导致下一个元素 of只是后续的递归调用，而每次都kle携带 的元素？xs有人可以帮助我理解这一点吗？

Answer 1

\n

是否是因为惰性评估，如果不需要的话，可以继续进行而无需真正计算？

\n

\n

或多或少，是的。

\n

如果你称它为kleene xsreturns [] : [\xe2\x80\xa6]，那么它是一个“cons”（列表数据对象），其中头已知，是一个空列表，并且仍然需要评估）。

\n

这意味着它可以毫无问题地生产第一个项目。因此可以在列表理解中使用。

\n

kleene xs因此， for 的第一项是[]，对于 的任何值xs，因此在列表推导式中，[]:[kle++[x] | kle <- kleene xs, x <- xs]它会采用kle = []然后开始枚举列表，因此如果xs = [1,2]，那么它将产生kle ++ [1]和kle ++ [2]，所以[1]和[2]。然后它移动到下一个项目，这将强制在递归调用中生成下一个项目，但是我们可以，这些是[1]和[2]并且这些可以在没有任何递归调用的情况下生成kleene xs。之后它将进行额外的递归调用。

\n

这使得它效率不高。它会随着长度为n的列表的(log ₂ n)级递归调用而增长。我们可以通过简单地引用我们正在构建的相同列表来优化它。的确：

\n

kleene :: [a] -> [[a]]\nkleene xs = go\n  where go = [] : [kle++[x] | kle <- go, x <- xs]\n

\n

现在，我们只进行一次调用，列表中下一项的生产者也将从同一列表中读取项目。这样做的缺点是它需要内存。kle <- go事实上，它将容纳我们需要的当前位置和我们正在生产的位置之间的所有物品。

\n