haskell - 为什么尾递归模数可以优化？

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) 计算堆栈，它将创建顶部 :首先，然后填充其正确的插槽，以迭代方式在恒定堆栈空间中工作(就像 Wikipedia 代码片段所示)。

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