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

Question

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

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

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

练习之一是实现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>如果我们对第一个元素的值不感兴趣。

列表理解也是惰性的。事实上，如果我们与:

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

它将从其中一项 x 的那一刻起终止在 xs有False作为p x .但是，如果您添加过滤器 p x , 它只会发出 True确实如此:

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

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