为什么可以优化尾递归Modulo 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 : []

输入列表的其余部分甚至没有被计算，因为take不需要它map，因此不需要输入列表中的更多元素。

旁注：TRMC 是急切评估语言的术语。在 Haskell 中，它被称为保护递归。递归调用必须在惰性构造函数后面。

我不相信 Haskell（即 GHC）在严格的构造函数情况下具有 TRMC 优化。如果结果类型是幺半群，它可能会像列表一样：

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

因此，在具有 TRMCO 的急切语言中，与其首先评估顶部的两个参数:确实像第二个片段暗示的那样打开 O(n) 计算堆栈，而是:先创建顶部，然后填充其正确的插槽，在一个恒定堆栈空间中的迭代方式（就像维基百科代码片段所示）。

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