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

Question

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

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

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

索引函数定义如下：

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

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

Answer 1

many times is (+ 1) function computed in the following code?

只计算一次。 map 不会强制对结果列表中的元素计算 f x<sub>i</sub>。这些计算被推迟（就像 Haskell 中的所有其他计算一样），只有当我们需要计算特定项目的价值时，我们才会这样做。

map在chapter 9 of the Haskell'10 report中指定为：

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

这里没有 seq、bang 模式等强制计算 f x，所以 map 函数确实 "yield" 和 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]，但它不计算 f x<sub> i</sub> 个元素，该计算将推迟到我们实际需要该列表中的值并对其执行某些操作（例如打印它）。

考虑到 f 是一个昂贵的函数，我们只需要列表中少量元素的值，这可以显着提高性能。

Answer 2

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

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

现在，我们将在每次调用 lambda 表达式时执行完全安全的 IO 操作。当我们在 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 次。

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

How many times is (+ 1) computed here?

haskell

functional-programming

lazy-evaluation

ghc