例如,这不是尾叫:
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有关,但我仍然不太了解:(
因为:
很懒。它本身不会触发对第二个参数的评估。
您展示的不是全部。 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中,当构造函数是惰性的并且无论如何都不会触发参数评估时,所有这些都不适用。