基于列表推导与递归理解Haskell无限列表的工作机制

这个函数能正常运行的核心就是Haskell的非严格（懒）求值——只在需要的时候计算表达式，且仅计算到满足需求的程度，不会提前展开所有递归。

先拆解函数定义：

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

它把克林闭包拆成两部分：

1. 首元素是空列表[]，对应克林闭包中长度为0的字符串；
2. 后续的列表推导式，负责生成所有长度≥1的字符串：遍历kleene xs的每个已有元素kle，将其与字母表xs的每个元素x拼接，得到长度+1的新字符串。

求值过程的分步解析 #

当你调用take 20 $ kleene [1,2,3]时，Haskell不会立刻展开整个递归，而是生成一个惰性列表：开头是[]，后面跟着待计算的延迟表达式（thunk）。它会按需逐步计算：

1. 首先拿到第一个元素[]——这是直接定义的，不需要任何递归计算；
2. 当需要第二个元素时，才会处理列表推导式的第一个迭代：从kleene xs中取已生成的第一个元素（也就是[]），遍历xs的每个元素，拼接得到[1]、[2]、[3]——这就是输出的第2到第4个元素；
3. 当需要第5个元素时，继续从kleene xs中取下一个已生成的元素（也就是[1]），和xs的每个元素拼接得到[1,1]、[1,2]、[1,3]；
4. 以此类推：每次都用kleene xs已经生成好的短字符串，生成一批更长的字符串，直到满足take 20的需求为止。

你代入时的误区 #

你误以为要先把整个kleene xs完全展开，但实际上：

• 列表推导式中的kle <- kleene xs是逐个取kleene xs的元素，而kleene xs本身是惰性生成的——每次只生成当前需要的元素，不会一次性展开整个无限递归；
• 当计算kle++[x]时，kle是kleene xs已经生成好的具体元素（比如[]、[1]等），而不是整个kleene xs表达式本身。因此不会出现你担心的“无限长元素”，只会生成长度逐步递增的字符串。

对比你熟悉的语言 #

• 和C的严格求值不同：C会立刻展开递归调用，这种写法会直接栈溢出或死循环；
• 和Prolog的回溯机制类似：Prolog不会一次性生成所有可能解，而是按需回溯生成，Haskell的懒求值也是按需生成元素，避免了不必要的计算。

内容的提问来源于stack exchange，提问作者Vrantamar