Haskell非严格求值解析：两个递归filter实现的差异及相关疑问

求值逻辑的核心区别 #

首先明确Haskell非严格（惰性）求值的核心规则：只要能返回部分可用的结构，就不会先求值全部子表达式。两个实现的差异完全围绕这个规则展开：

第一个实现（标准filter） #

属于生成式递归，求值逻辑如下：

• 匹配到非空列表时，先判断头部是否满足谓词条件
• 如果满足，直接返回h : 递归调用结果的cons结构。Haskell的列表cons(:)是惰性构造器，这个结构不需要等后面的递归调用跑完就能先返回外层的cons壳：外层代码如果只需要取第一个元素，直接就能拿到h，后面的递归thunk永远不会被求值。
• 所以它支持处理无限列表，比如take 3 $ recFilter even [1..]可以正常返回[2,4,6]，不需要遍历完整个无限列表，完全符合非严格规则。

第二个实现 #

属于尾递归实现，有两个完全违背非严格规则的设计：

1. 所有递归调用都是函数的最后一个操作，在len参数减到0之前，不会返回任何部分构造的列表结构，必须等全部递归执行完成才会一次性返回最终的xs结果。哪怕你只需要结果的第一个元素，也必须等所有len次递归跑完。
2. 用到了tl ++ [h]列表拼接操作，这个操作本身就必须遍历完整个tl列表才能完成，天然就是严格的。
   另外这个实现本身功能也不符合filter语义：它是遍历原列表前len个元素，把满足条件的元素追加到列表末尾，还有O(n²)的时间复杂度问题。

相关疑问解答 #

1. 是否可以写出非严格的尾递归函数？ #

常规写法下不能。
尾递归的要求是「递归调用是函数的最后一步操作，函数返回值等于递归调用的返回值」，而非严格的函数需要在递归调用外包裹惰性构造器（比如列表的cons）来返回部分结构，这时候最后一步操作就变成了构造器应用，不再是递归调用，自然也就不符合尾递归的要求。
当然有一些进阶技巧比如用差分列表、惰性累加器可以实现近似的效果，但本质上已经不属于常规纯尾递归的范畴，性能也未必比普通生成式递归更好。

2. 如何在GHCi中查看第一个实现的调用过程，观察h:的行为？ #

可以用GHCi内置的调试工具，步骤如下：

• 将第一个recFilter的代码保存为.hs文件，在GHCi中用:load 文件名加载
• 输入:break recFilter给函数打上断点
• 执行测试调用，比如head $ recFilter even [1,2,3,4]，GHCi会在每次进入recFilter函数时停下
• 用:step命令单步执行，你可以清楚看到：当匹配到元素2之后，直接就返回了结果，根本不会执行后续对3、4的递归操作。
• 如果你执行的是完整的recFilter even [1,2,3,4]，可以用:print <变量名>命令查看未求值的thunk状态，就能看到h:生成的cons结构里，后半部分是还没求值的递归调用占位符。

额外解释你疑惑的h:结果去向：惰性求值下，h : recFilter p tl不会等后面的递归完成，会直接生成一个(h, <thunk>)的结构返回给上层调用者，只有当上层需要访问列表的下一个元素时，才会触发里的递归调用求值。 #

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