这里计算（+1）多少次？

Question

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

以下代码中，（+ 1）个函数计算了多少次？

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

索引函数的定义如下：

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

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

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函数的确会“屈服” 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]最终映射到一个列表[f x1, f x2, ..., f xn]，但它并不能计算的元素，即计算被推迟，直到我们真正需要在该列表中的值，用它做的东西（如priting它）。f xi

给定f昂贵的功能，这可以显着提高性能，并且我们只需要列表中少量元素的值即可。

Answer 2

让我们通过做一些可怕的事情来测试它。您需要为此导入Debug.Trace模块。

ghci> (map (\x -> trace "Performing..." (x + 1)) [1..10]) !! 5

现在，我们将IO在每次调用lambda表达式时采取完全安全的措施。当我们在GHCi中运行时，我们得到

Performing
7

所以只有一次。

作为健全性检查，我们可以将其除去!! 5。

ghci> map (\x -> trace "Performing..." (x + 1)) [1..10]
[Performing
2,Performing
3,Performing
4,Performing
5,Performing
6,Performing
7,Performing
8,Performing
9,Performing
10,Performing
11]

因此，当我们要求整个列表时，肯定发生了10次。