为什么要优化尾递归模态？

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优化功能。如果结果类型是一个monoid，它可能确实像列表一样：

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

所以用TRMCO急切的语言，而不是像第二个代码段所暗示的那样，首先对顶:的两个参数的确开放了O（n）计算堆栈，而是先创建顶:并填充然后在其右边的插槽中以不变的方式在恒定的堆栈空间中工作（就像Wikipedia代码片段所示）。

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