haskell - (+ 1) 这里计算了多少次？

Question

在我的函数式编程考试中，我有以下问题：

(+ 1) 函数在以下代码中计算了多少次？

(map (+ 1) [1 .. 10]) !! 5

索引函数的定义如下：

(h:_) !! 0 = h
(_:t) !! x = t !! (x-1)

我会说 6 次，但正确答案似乎是 1，我不明白为什么。我在 Haskell 中找不到关于惰性求值的足够好的解释，所以我想知道正确答案是什么以及为什么。先感谢您！

标签： haskellfunctional-programminglazy-evaluationghc

Answer 1

(+ 1)函数在下面的代码中计算了多少次？

它只计算一次。map不强制计算结果列表中的元素。这些计算被推迟了（就像 Haskell 中的其他一切一样），只有当我们需要计算特定项目的值时，我们才会这样做。f xi

map在 Haskell'10 报告的第 9 章中指定为：

-- Map and append  
map :: (a -> b) -> [a] -> [b]  
map f []     = []  
map f (x:xs) = f x : map f xs

这里没有seq, bang 模式等来强制评估f x，因此该map函数确实会“产生” an f x，但是如果没有评估f x，它会被推迟到有必要时（并且可能会发生我们对其中一些不感兴趣的情况值，因此可以节省一些 CPU 周期）。

我们可以看看 Haskell 将如何评估这一点：

   (!!) (map (+ 1) [1 .. 10]) 5
-> (!!) ((+1) 1 : map (+1) [2..10]) 5
-> (!!) (map (+1) [2..10]) 4
-> (!!) ((+1) 1 : map (+1) [3..10]) 4
-> (!!) (map (+1) [3..10]) 3
-> (!!) ((+1) 1 : map (+1) [4..10]) 3
-> (!!) (map (+1) [4..10]) 2
-> (!!) ((+1) 1 : map (+1) [5..10]) 2
-> (!!) (map (+1) [5..10]) 1
-> (!!) ((+1) 1 : map (+1) [6..10]) 1
-> (!!) (map (+1) [6..10]) 0
-> (!!) ((+1) 6 : map (+1) [7..10]) 0
-> (+1) 6
-> 7

这是因为map f [x1, x2, ..., xn]最终映射到一个 list [f x1, f x2, ..., f xn]，但它不计算元素，该计算被推迟，直到我们真正需要该列表中的值，并对它做一些事情（比如打印它）。f xi

这可以带来显着的性能提升，因为f这是一个昂贵的函数，而且我们只需要列表中少量元素的值。