为什么尾递归模块化可以被优化？

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有关，但我仍然无法理解它 :(

- Kk Shinkai

---

这里没有优化，只有惰性求值。 - Will Ness

你的“为什么不”开头看起来与你的“工作原理”完全相同，除了一些多余的括号外，其余部分只是语法糖。 - Joseph Sible-Reinstate Monica

@JosephSible-ReinstateMonica，他们打算用 [...] 来表示一个完整的列表，这是我的理解。 - Will Ness

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的急切语言中，不是首先对顶部的两个参数进行评估，而是创建顶部: ，然后填充其右侧插槽，以迭代方式在恒定堆栈空间中工作（就像维基百科代码片段所显示的那样）。但是，在Haskell中，当构造函数是惰性的且没有触发自己的参数评估时，所有这些都不适用。

- Will Ness