6

例如，这不是尾调用：

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有关，但我仍然不能很好地理解它:(

4

1 回答 1

8

因为:很懒。它本身不会触发对其第二个参数的评估。

你所展示的并不是故事的全部。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 中，这一切都不适用，当构造函数是惰性的并且无论如何都不会触发任何参数评估时。

于 2020-03-01T12:10:30.253 回答