Haskell中pack'可处理无限列表而pack无法终止的原因是什么？

你遇到的差异本质是左折叠foldl的求值特性和惰性结构递归的差异，和let-in语法、reverse的实现没有关系：

• foldl天生无法处理无限列表
  foldl的求值逻辑是逐层向内嵌套：

foldl f z [x1, x2, x3...] = f (...(f (f z x1) x2) x3...) ...

惰性求值下，要获取foldl返回结果的最外层结构，必须先遍历完输入列表的所有元素，完成所有内层f调用的规约。输入是无限列表时，遍历永远不会结束，foldl永远无法返回任何可用结果。哪怕你删除reverse逻辑，直接返回foldl的结果，运行时依然会挂起，和你修改reverse的实现完全无关。
你认为“左折叠支持无限列表”是普遍误解，只有右折叠foldr可以在遍历过程中逐步返回外层构造器，从而处理无限列表。

• pack'适配惰性求值规则，可处理无限列表
  pack'用的是原生的结构递归，完全匹配Haskell的惰性求值逻辑：

pack' (x:xs) = let (first,rest) = span (==x) xs
  in (x:first) : pack' rest

当你调用head $ pack' [1..]时，求值器只需要获取返回列表的第一个元素：

1. 匹配到输入(x:xs)的分支，直接可以得到返回结果的最外层构造器(:)
2. 第一个子列表(x:first)只需要取到外层的列表构造器即可满足head的求值需求，不需要完全计算span遍历整个无限列表
3. 后面的pack' rest根本不会被求值，整个过程只需要有限步就能返回结果
   另外span本身也是惰性实现，不会强制遍历完整个输入列表，只要按需取出满足条件的前缀部分即可，进一步保证了无限列表下的可用性。

内容的提问来源于stack exchange，提问作者Anthony D'Arienzo