Haskell 中的 `map` 是懒惰的吗？

Question

我一直在研究 Haskell 中的 Graham Hutton 的编程。它指出

the function map applies a function to all elements of a list

好的，有道理。当然符合我对其他语言地图的了解。

练习之一是实现 all :: (a -> Bool) -> [a] -> Bool。

有时候，如果不懒惰地完成，天真的实现可能会无限循环。例如 all (<10) [1..]。所以我的第一个实现是：

all p []       = True
all p (x:xs)   | not (p x) = False
               | otherwise = all' p xs

但后来我考虑尝试使用 map 和 and 的函数组合，看看 Haskell 中的非终止程序会做什么：

all' :: (a -> Bool) -> [a] -> Bool
all' p = and . map p

令我惊讶的是，all' (<10) [1..] 很快就返回了 False。我实际上期望 map 在应用 and 之前尝试创建一个无限列表 - 类似于 and [p x | x <- xs, p x].

这种终止行为意味着 map 实际上正在创建类似于 and 正在处理的流。 map 实际上是懒惰的（因此描述是错误的）还是我在我的第二个实现中误解了其他东西？

Answer 1

Is map in fact lazy (and hence the description wrong) or have I misunderstood something else in my second implementation?

map 懒惰。它不会急于将功能应用于每个项目。事实上，所有表达式都是惰性的，因为 map f x 保持 map f xs 除非需要该值。

如果我们评估map f xs，并且我们需要例如第三个元素，它不会确定f x<sub>1</sub> if我们对第一个元素的 value 不感兴趣。

列表理解也是懒惰的。事实上，如果我们使用：

and [<strong>p x</strong> | x <- xs]

它将从 xs 中的一项 x 具有 False 为 p x 的那一刻起终止。但是，如果您添加过滤器 p x，它只会发出 Trues，实际上：

[<strong>p x</strong> | x <- xs, <b>p x</b>]

只会产生 True，因为我们已经过滤了 p x 应该是 True 的事实，而 and 在无限 True 的列表永远不会终止，因为 and 将继续寻找 False 值。

Is `map` in Haskell lazy?