为什么尾部递归模块Cons可以优化

Question

例如，这不是尾调用：

map _ [] = []
map f (x : xs) = f x : map f xs

递归调用由(:)数据构造函数保护，因此它不会像其他语言中的对等调用那样构建庞大的堆栈。它的工作原理如下：

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : 3 : map (+1) (3 : [])
2 : 3 : 4 : map (+1) []
2 : 3 : 4 : []

为什么不

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : (3 : map (+1) (3 : []))
2 : (3 : (4 : map (+1) []))
2 : (3 : (4 : []))
2 : (3 : [4])
2 : [3, 4]
[2, 3, 4]

这与WHNF有关，但我仍然不能很好地理解它：(

Answer 1

因为:是惰性的。它本身不会触发对其第二个论点的评估。

你展示的并不是故事的全部。map也不会单独执行您显示的内容，只有在其他消费者提出要求时，main(或GHCi的REPL(才会最终要求其结果。例如，

GHCi> take 2 (map (1+) [1..4]
{- implied `putStrLn . show` causes this -}
= take 2 (2 : map (1+) (enumFromTo 2 4))
= 2 : take 1 (map (1+) (enumFromTo 2 4))
= 2 : take 1 (3 : map (1+) (enumFromTo 3 4))
= 2 : 3 : take 0 (map (1+) (enumFromTo 3 4))
= 2 : 3 : []

输入列表的其余部分甚至不被计算，因为CCD_ 5不从CCD_。

附带说明：TRMC渴望评估语言的术语。在Haskell中，它被称为保护递归。递归调用必须位于惰性构造函数后面。

我不相信Haskell(即GHC(在严格的构造函数情况下有TRMC优化。如果结果类型是monoid，它可以像列表一样：

[a] ++ ([b] ++ ([c] ++ ....))
=
([a] ++ [b]) ++ ([c] ++ ....)

因此，在TRMCO的一种热切的语言中，它不会像第二个代码片段所暗示的那样，首先评估顶部:的两个参数，实际上打开了一个O(n(计算堆栈，而是会先创建顶部:，然后填充它的右槽，在恒定的堆栈空间中以迭代的方式工作(就像维基百科代码片段所显示的那样(。

但在Haskell中，当构造函数是惰性的，并且无论如何都不会单独触发参数求值时，所有这些都不适用。