关于Haskell中foldr处理无限列表的疑问（基于LYAH阅读）

首先要纠正一个关键误解：foldr (:) [] [1..]实际上完全等价于原无限列表[1..]，你觉得“实际并非如此”只是因为GHCi的求值和打印策略导致的视觉差异，我们一步步拆解来看：

为什么foldr (:) [] 是列表的恒等操作？ #

先回忆foldr的定义：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

当我们用(:)作为折叠函数，[]作为初始值时：

• 对于空列表，结果是[]；
• 对于x:xs，结果是x : foldr (:) [] xs。

递归展开下去，不管输入列表是有限还是无限，这个表达式都会原封不动地重建输入列表。比如：

• 有限列表[1,2,3]会变成1 : (2 : (3 : []))，也就是原列表；
• 无限列表[1..]会变成1 : (2 : (3 : (...)))，和原无限列表的结构完全一致。

那为什么GHCi里输入foldr (:) [] [1..]，只会输出1 :然后卡住？这是因为GHCi默认采用**弱头范式（WHNF）**求值：它只会计算到最外层的构造器（这里就是:），然后等待用户输入或者停止打印。但这并不代表结果不等于原列表——你可以用take来验证：

ghci> take 5 $ foldr (:) [] [1..]
[1,2,3,4,5]
ghci> take 5 [1..]
[1,2,3,4,5]

两者结果完全相同，证明它们是同一个无限列表。

GHCi是“识别”出[1..]是无限列表吗？ #

答案是否定的——GHCi并没有提前“识别”这个列表是无限的，而是[1..]本身的定义就是一个惰性求值的无限结构：

• [1..]是enumFrom 1的语法糖，而Integer类型的Enum实例中，enumFrom的实现是递归生成下一个元素的：enumFrom n = n : enumFrom (n+1)。
• Haskell的惰性求值意味着，只有当需要某个元素时，才会去计算它。对于enumFrom 1，它不会一次性生成所有元素，而是每次需要下一个元素时，才计算n+1并拼接成新的列表节点。

类型推断在这里的作用是确定enumFrom使用哪个Enum实例（比如这里是Integer），但它和判断列表是否无限没有关系。GHCi不需要提前知道列表是无限的，只是在求值过程中，发现每次请求下一个元素都会触发新的计算，而这个计算永远不会终止，所以就表现为无限列表。

总结 #

1. foldr (:) [] [1..]和[1..]是完全等价的无限列表，GHCi的打印方式只是让你看不到完整结果；
2. [1..]的无限性来自其本身的惰性定义，而非GHCi的“提前识别”；
3. 类型推断负责确定表达式的类型实例，和列表是否无限无关。

内容的提问来源于stack exchange，提问作者J. Kim