我学习Haskell是从一个命令式（主要是C）编程pov开始的，对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],...]但它应该永远持续下去。为什么我得到的输出越来越大，而不是无限大的元素？是不是因为懒惰求值，每个递归调用都算作列表的一个元素，所以kle的下一个元素只是随后的递归调用，而每次都携带xs的元素？有人能帮我理解这一点吗？
1条答案
按热度按时间zzlelutf1#
是不是因为懒惰的评估，如果不需要的话，允许在没有真正计算的情况下继续下去？
或多或少是的。
如果你调用
kleene xs，它返回[] : […]，所以它是一个“cons”（一个列表数据对象），其中头部是已知的，一个空列表，还有一些东西需要评估）。因此，这意味着它可以毫无问题地生产第一物品。因此可以在列表理解中使用。
kleene xs的第一个元素是[]，对于xs的任何值，所以在列表解析[]:[kle++[x] | kle <- kleene xs, x <- xs]中，它接受kle = []，然后开始枚举列表，所以如果xs = [1,2]，那么它将产生kle ++ [1]和kle ++ [2]，所以[1]和[2]。然后它移动到下一项，这将强制在递归调用中生成下一项，但我们可以，这些是[1]和[2]，这些可以在没有任何递归调用kleene xs的情况下生成。在此之后，它将进行额外的递归调用。这使得它不是很有效。对于𝓞长度为 n 的列表，它将随着 （log2n） 级的递归调用而增长。我们可以通过简单地引用我们正在构造的 * 相同 * 列表来优化它。的确：
现在，我们只进行一次调用，列表中下一个项目的生产者也将从同一个列表中读取项目。这样做的缺点是它需要内存。实际上，它将保存我们需要的
kle <- go的当前位置和我们正在生成的位置之间的所有项目。