在同一个列表上两次调用 map 会强制遍历列表两次吗？
Does calling map twice on the same list forces iterate through the list twice?
我完全是 Haskell 的新手，在阅读教程时我发现了类似的东西
Thanks to Haskell's laziness, even if you map something over a list
several times and filter it several times, it will only pass over the
list once.
这是我简单的愚蠢示例：x = map foo (map foo [1,2]) where foo p = p * 2
现在，我想到了两个问题。
- 为什么要感谢懒惰？我知道懒惰意味着它不会评估表达式直到它必须但是......它如何强制迭代列表一次而不是声明的 maps/filters?
- 如何验证它只迭代一次？
- 奖金问题 - 我知道副作用是但是......如果我能打印一些东西来调试就太好了，例如
foo p =
let printResult = print "Some helpful message"
in p * 2
Why is it thanks to laziness? I know that laziness means that it does not evaluate expression till it has to but... How does it force iterating list once instead of declared number of maps/filters?
如果您只对列表的第一个元素感兴趣，map 不会评估列表的其余部分。
假设您有兴趣评估 map foo (map foo [1,2]) 以达到正常形式。然后它将调用 map foo (map foo [1,2]).
map :: (a -> b) -> [a] -> [b] is implemented as [src]:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
因此它会将子表达式 map foo [1,2] 计算为头部范式：它必须知道外部项是空列表数据构造函数 [] 还是“cons” (_:_).
因此它将评估第二个映射，但仅限于外部数据构造函数。这意味着它将看到列表 [1,2] 不为空，因此它将产生 foo 1 : map foo [2]。它 不会 评估 foo 1，因为这也不是必需的。
因为我们现在知道子表达式有一个“cons”作为数据构造函数，所以外部映射函数将 return foo (foo 1) : map foo (map foo [2])。它因此将原始列表的“光标”进一步移动了一步，但它不会枚举整个列表，也不会计算元素上的函数foo。
如果我们要打印 head 作为示例，例如 print (head (map foo (map foo [1,2])))，这意味着 head 将被计算，而 head (foo (foo 1) : map foo (map foo [2])) 将只计算 return foo (foo 1)。它将再次 而不是 评估 foo (foo 1)。现在 print 将需要评估第一项，因为它应该将其打印到输出通道，这意味着它评估 foo (foo 1)。为了计算 foo (foo 1)，它首先必须计算 foo 1，因为这是强制计算乘法所必需的，所以 foo 1 被计算为 2，并且 foo 2 被评估为 4.
但我们因此通过不评估整个列表或其他元素的 foo (foo …) 部分而节省了很多周期。
How can I verify that it iterates only once?
像 vizualize-cbn [GitHub] and ghc-viz [Hackage] 这样的工具可以帮助直观地了解 Haskell 如何处理懒惰。人们可以看到对一个元素的评估如何导致可视化其他元素，从而帮助理解递归模式。
Bonus question - I know that side effections are but... It would be pretty nice if I can print something to debug e.g.
可以利用trace :: String -> a -> a来打印信息，例如：
import Debug.Trace(<strong>trace</strong>)
foo p = <strong>trace</strong> "evaluated foo" (p * 2)
如果您随后计算 print (head (map foo (map foo [1,2])))，您会看到它只计算 foo 两次，而不是四次。确实：
ghci> import Debug.Trace(trace)
ghci> foo p = trace "evaluated foo" (p * 2)
ghci> print (head (map foo (map foo [1,2])))
evaluated foo
evaluated foo
4
另一个答案中没有明确涵盖的一点是，是一种意义上的懒惰意味着“即使你多次在列表上映射某些东西并且多次过滤，它只会通过列表一次。
让我们看看当我们评估 map foo (map foo [1, 2, 3]) 时会发生什么，而不是像 Willem Van Onsem 的回答中那样消费者是 head，假设我们正在 printing 它所以我们需要评估整个事情。
虽然我不想详细追踪 print 的实际评估，但让我们假设我们有一个特殊用途的 print 列表，看起来像这样（ putStr 是原始的）：
print :: Show a => [a] -> IO ()
print [] = putStr "[]"
print (x : xs) = putStr "[" >> putStr (show x) >> print_rest xs
where print_rest [] = putStr "]"
print_rest (x : xs) = putStr ", " >> putStr (show x) >> print_rest xs
当然还有：
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
并且：
foo p = p * 2
所以，我们从：
开始
print (map foo (map foo [1, 2, 3]))
这当然是真的：1
print (map foo (map foo (1 : 2 : 3 : []) ))
print 需要模式匹配其参数，这需要强制外部 map。外部 map 反过来首先需要知道它的参数是否为空，从而强制调用内部 map 。内部映射也需要模式匹配它的参数，但这是一个非空的具体列表。所以现在我们可以 return 向上模式匹配堆栈并得到这个：
print (map foo (map foo (1 : 2 : 3 : []) ))
print (map foo (foo 1 : map foo (2 : 3 : []) ))
print (foo (foo 1) : map foo (map foo (2 : 3 : []) ))
putStr "[" >> putStr (show (foo (foo 1))) >> print_rest (map foo (map foo (2 : 3 : []) ))
现在我们得到了 IO 驱动程序可以使用的东西（一个 putStr 调用）。所以它可以假设，导致控制台输出显示：
[
我们只剩下表达式：
putStr (show (foo (foo 1))) >> print_rest (map foo (map foo (2 : 3 : []) ))
前面还有一个putStr；这个只需要给力show (foo (foo 1))。 show 不得不强制 foo (foo 1)，这不得不强制 foo 1 到 2；那么外面的 foo 可以产生 4 所以 show 可以产生 "4".
putStr "4" >> print_rest (map foo (map foo (2 : 3 : []) ))
让 IO 消耗我们现在在控制台上的输出：
[4
并留下这个表达式：
print_rest (map foo (map foo (2 : 3 : []) ))
通过与上面相同的过程，我们可以去：
print_rest (map foo (map foo (2 : 3 : []) ))
print_rest (map foo (foo 2 : map foo (3 : []) ))
print_rest (foo (foo 2) : map foo (map foo (3 : []) ))
putStr "," >> putStr (show (foo (foo 2))) >> print_rest (map foo (map foo (3 : []) ))
putStr "," >> putStr (show (foo 4)) >> print_rest (map foo (map foo (3 : []) ))
putStr "," >> putStr (show 8) >> print_rest (map foo (map foo (3 : []) ))
putStr "," >> putStr "8" >> print_rest (map foo (map foo (3 : []) ))
然后 IO 驱动程序可以使用 putStr 调用所以我们看到：
[4, 8
剩下要计算的表达式：
print_rest (map foo (map foo (3 : []) ))
变成（现在跳过一些步骤）：
putStr "," >> putStr (show (foo (foo 3))) >> print_rest (map foo (map foo [] ))
putStr "," >> putStr "12" >> print_rest (map foo (map foo [] ))
IO 做了一件神奇的事情，以便我们可以在控制台上看到：
[4, 8, 12
最后残差 print_rest (map foo (map foo [] )) 非常直接地计算为 putStr "]" 所以我们终于可以看到：
[4, 8, 12]
现在，让我们回顾一下发生的事情。
懒惰评估意味着我们在需要之前不评估任何东西，而“需要”最终来自 IO 需要评估事物的驱动程序，直到它具有具有完全评估参数的具体原语，以便它可以实际上 做 一些事情。这就是为什么我选择了评估事物的顺序。
如果你仔细看一下，你会注意到我们从来没有产生过像 map foo [2, 4, 6] 这样的表达式。我们评估了 both of the foo calls on the first element of the list before any of the mapping or printing even pattern matched to see if there was 列表的第二个元素。这也意味着列表的第一个元素（以及 fooing 它的两个结果）变得未被引用，并且可以在检查列表的第二个元素之前被垃圾收集器回收。然后列表的第二个元素在第三个被检查之前被完全处理。
这就是懒惰评估嵌套映射、过滤器等的意义，只需要遍历一次基本列表。有时，与对相同的嵌套映射、过滤器等进行急切求值相比，这可能会带来巨大的效率提升。例如，如果基本列表不是像 [1, 2, 3] 这样的小型具体列表，而是一个会延迟生成的表达式一个非常大的（甚至是无限的！）列表，那么我们的整个“多遍”映射序列可以一次只用一个元素的足够内存进行操作，而不需要生成完整的基本序列，然后生成完整的序列在下一阶段，依此类推。这也意味着我们立即生成和消耗一个值的所有中间阶段，增加了我们在 CPU 缓存或垃圾收集器堆的最短寿命最有效生成中工作的机会。
但是，如果您仔细观察，您会注意到，即使我们“只遍历列表一次”，我们仍然拥有完全相同的 : 构造函数应用程序，如果我们有完全评估 map foo [1, 2, 3] 到 [2, 4, 6] 然后遍历它。我们仍然为 foo 1 : _ 分配了一个构造函数单元，然后立即使用它并分配了 foo 2 : _.
所以在另一种意义上“懒惰意味着我们只遍历列表一次”是不正确的。当我们最终使用整个列表时（而不是使用 head 或 take 只检查其中的一部分），那么惰性求值的结果完全相同（意味着分配和模式匹配）如果我们确实对每个阶段进行了整体评估，然后遍历下一阶段的结果。我们已经 重新安排了 工作，惰性评估产生的顺序通常 更好 ，但我们没有从根本上改变我们的工作量必须要做。中间列表在某种意义上仍然存在，即使它们从未同时出现在内存中。
幸运的是，在许多情况下，GHC 有许多其他优化可以避免实际创建中间列表单元格（或实际上是基本列表！）。例如，GHC 可以识别 map foo (map bar xs) 等同于 map (foo . bar) xs，它没有中间列表来遍历或分配我们是惰性评估还是热切评估。特别简单的情况，如我使用的示例，将大量内联，并且可能最终编译为直接打印 [4, 8, 12] 而无需分配或评估任何内容。
TLDR: 从某种意义上说，当您链接映射和过滤器等函数时，惰性求值确实避免了重复遍历中间列表。因此，OP 中的引述很可能是准确的（取决于其作者的意图），但存在重要的细微差别，重要的是不要过度推销它。
当需要整个结果时，那些遍历的工作仍然完成；惰性评估只是重新安排工作完成的顺序。如果它允许您大大减少中间结果消耗的内存，这仍然是一个巨大的胜利，因为它们现在可能不必一次全部出现在内存中。
1 请记住，列表的方括号语法只是人类写出一个真正在内存中表示为嵌套系列应用程序的序列的好方法: 构造函数，由 [] 构造函数终止。 [1, 2, 3] 是 1 : (2 : (3 : []))，我们不需要那些内括号，因为 : 构造函数是中缀和右结合的，所以我们可以写成 1 : 2 : 3 : [].
我完全是 Haskell 的新手，在阅读教程时我发现了类似的东西
Thanks to Haskell's laziness, even if you map something over a list several times and filter it several times, it will only pass over the list once.
这是我简单的愚蠢示例：x = map foo (map foo [1,2]) where foo p = p * 2
现在，我想到了两个问题。
- 为什么要感谢懒惰？我知道懒惰意味着它不会评估表达式直到它必须但是......它如何强制迭代列表一次而不是声明的 maps/filters?
- 如何验证它只迭代一次？
- 奖金问题 - 我知道副作用是但是......如果我能打印一些东西来调试就太好了，例如
foo p =
let printResult = print "Some helpful message"
in p * 2
Why is it thanks to laziness? I know that laziness means that it does not evaluate expression till it has to but... How does it force iterating list once instead of declared number of maps/filters?
如果您只对列表的第一个元素感兴趣，map 不会评估列表的其余部分。
假设您有兴趣评估 map foo (map foo [1,2]) 以达到正常形式。然后它将调用 map foo (map foo [1,2]).
map :: (a -> b) -> [a] -> [b] is implemented as [src]:
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs
因此它会将子表达式 map foo [1,2] 计算为头部范式：它必须知道外部项是空列表数据构造函数 [] 还是“cons” (_:_).
因此它将评估第二个映射，但仅限于外部数据构造函数。这意味着它将看到列表 [1,2] 不为空，因此它将产生 foo 1 : map foo [2]。它 不会 评估 foo 1，因为这也不是必需的。
因为我们现在知道子表达式有一个“cons”作为数据构造函数，所以外部映射函数将 return foo (foo 1) : map foo (map foo [2])。它因此将原始列表的“光标”进一步移动了一步，但它不会枚举整个列表，也不会计算元素上的函数foo。
如果我们要打印 head 作为示例，例如 print (head (map foo (map foo [1,2])))，这意味着 head 将被计算，而 head (foo (foo 1) : map foo (map foo [2])) 将只计算 return foo (foo 1)。它将再次 而不是 评估 foo (foo 1)。现在 print 将需要评估第一项，因为它应该将其打印到输出通道，这意味着它评估 foo (foo 1)。为了计算 foo (foo 1)，它首先必须计算 foo 1，因为这是强制计算乘法所必需的，所以 foo 1 被计算为 2，并且 foo 2 被评估为 4.
但我们因此通过不评估整个列表或其他元素的 foo (foo …) 部分而节省了很多周期。
How can I verify that it iterates only once?
像 vizualize-cbn [GitHub] and ghc-viz [Hackage] 这样的工具可以帮助直观地了解 Haskell 如何处理懒惰。人们可以看到对一个元素的评估如何导致可视化其他元素，从而帮助理解递归模式。
Bonus question - I know that side effections are but... It would be pretty nice if I can print something to debug e.g.
可以利用trace :: String -> a -> a来打印信息，例如：
import Debug.Trace(<strong>trace</strong>)
foo p = <strong>trace</strong> "evaluated foo" (p * 2)
如果您随后计算 print (head (map foo (map foo [1,2])))，您会看到它只计算 foo 两次，而不是四次。确实：
ghci> import Debug.Trace(trace)
ghci> foo p = trace "evaluated foo" (p * 2)
ghci> print (head (map foo (map foo [1,2])))
evaluated foo
evaluated foo
4
另一个答案中没有明确涵盖的一点是，是一种意义上的懒惰意味着“即使你多次在列表上映射某些东西并且多次过滤，它只会通过列表一次。
让我们看看当我们评估 map foo (map foo [1, 2, 3]) 时会发生什么，而不是像 Willem Van Onsem 的回答中那样消费者是 head，假设我们正在 printing 它所以我们需要评估整个事情。
虽然我不想详细追踪 print 的实际评估，但让我们假设我们有一个特殊用途的 print 列表，看起来像这样（ putStr 是原始的）：
print :: Show a => [a] -> IO ()
print [] = putStr "[]"
print (x : xs) = putStr "[" >> putStr (show x) >> print_rest xs
where print_rest [] = putStr "]"
print_rest (x : xs) = putStr ", " >> putStr (show x) >> print_rest xs
当然还有：
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
并且：
foo p = p * 2
所以，我们从：
开始print (map foo (map foo [1, 2, 3]))
这当然是真的：1
print (map foo (map foo (1 : 2 : 3 : []) ))
print 需要模式匹配其参数，这需要强制外部 map。外部 map 反过来首先需要知道它的参数是否为空，从而强制调用内部 map 。内部映射也需要模式匹配它的参数，但这是一个非空的具体列表。所以现在我们可以 return 向上模式匹配堆栈并得到这个：
print (map foo (map foo (1 : 2 : 3 : []) ))
print (map foo (foo 1 : map foo (2 : 3 : []) ))
print (foo (foo 1) : map foo (map foo (2 : 3 : []) ))
putStr "[" >> putStr (show (foo (foo 1))) >> print_rest (map foo (map foo (2 : 3 : []) ))
现在我们得到了 IO 驱动程序可以使用的东西（一个 putStr 调用）。所以它可以假设，导致控制台输出显示：
[
我们只剩下表达式：
putStr (show (foo (foo 1))) >> print_rest (map foo (map foo (2 : 3 : []) ))
前面还有一个putStr；这个只需要给力show (foo (foo 1))。 show 不得不强制 foo (foo 1)，这不得不强制 foo 1 到 2；那么外面的 foo 可以产生 4 所以 show 可以产生 "4".
putStr "4" >> print_rest (map foo (map foo (2 : 3 : []) ))
让 IO 消耗我们现在在控制台上的输出：
[4
并留下这个表达式：
print_rest (map foo (map foo (2 : 3 : []) ))
通过与上面相同的过程，我们可以去：
print_rest (map foo (map foo (2 : 3 : []) ))
print_rest (map foo (foo 2 : map foo (3 : []) ))
print_rest (foo (foo 2) : map foo (map foo (3 : []) ))
putStr "," >> putStr (show (foo (foo 2))) >> print_rest (map foo (map foo (3 : []) ))
putStr "," >> putStr (show (foo 4)) >> print_rest (map foo (map foo (3 : []) ))
putStr "," >> putStr (show 8) >> print_rest (map foo (map foo (3 : []) ))
putStr "," >> putStr "8" >> print_rest (map foo (map foo (3 : []) ))
然后 IO 驱动程序可以使用 putStr 调用所以我们看到：
[4, 8
剩下要计算的表达式：
print_rest (map foo (map foo (3 : []) ))
变成（现在跳过一些步骤）：
putStr "," >> putStr (show (foo (foo 3))) >> print_rest (map foo (map foo [] ))
putStr "," >> putStr "12" >> print_rest (map foo (map foo [] ))
IO 做了一件神奇的事情，以便我们可以在控制台上看到：
[4, 8, 12
最后残差 print_rest (map foo (map foo [] )) 非常直接地计算为 putStr "]" 所以我们终于可以看到：
[4, 8, 12]
现在，让我们回顾一下发生的事情。
懒惰评估意味着我们在需要之前不评估任何东西，而“需要”最终来自 IO 需要评估事物的驱动程序，直到它具有具有完全评估参数的具体原语，以便它可以实际上 做 一些事情。这就是为什么我选择了评估事物的顺序。
如果你仔细看一下，你会注意到我们从来没有产生过像 map foo [2, 4, 6] 这样的表达式。我们评估了 both of the foo calls on the first element of the list before any of the mapping or printing even pattern matched to see if there was 列表的第二个元素。这也意味着列表的第一个元素（以及 fooing 它的两个结果）变得未被引用，并且可以在检查列表的第二个元素之前被垃圾收集器回收。然后列表的第二个元素在第三个被检查之前被完全处理。
这就是懒惰评估嵌套映射、过滤器等的意义，只需要遍历一次基本列表。有时，与对相同的嵌套映射、过滤器等进行急切求值相比，这可能会带来巨大的效率提升。例如，如果基本列表不是像 [1, 2, 3] 这样的小型具体列表，而是一个会延迟生成的表达式一个非常大的（甚至是无限的！）列表，那么我们的整个“多遍”映射序列可以一次只用一个元素的足够内存进行操作，而不需要生成完整的基本序列，然后生成完整的序列在下一阶段，依此类推。这也意味着我们立即生成和消耗一个值的所有中间阶段，增加了我们在 CPU 缓存或垃圾收集器堆的最短寿命最有效生成中工作的机会。
但是，如果您仔细观察，您会注意到，即使我们“只遍历列表一次”，我们仍然拥有完全相同的 : 构造函数应用程序，如果我们有完全评估 map foo [1, 2, 3] 到 [2, 4, 6] 然后遍历它。我们仍然为 foo 1 : _ 分配了一个构造函数单元，然后立即使用它并分配了 foo 2 : _.
所以在另一种意义上“懒惰意味着我们只遍历列表一次”是不正确的。当我们最终使用整个列表时（而不是使用 head 或 take 只检查其中的一部分），那么惰性求值的结果完全相同（意味着分配和模式匹配）如果我们确实对每个阶段进行了整体评估，然后遍历下一阶段的结果。我们已经 重新安排了 工作，惰性评估产生的顺序通常 更好 ，但我们没有从根本上改变我们的工作量必须要做。中间列表在某种意义上仍然存在，即使它们从未同时出现在内存中。
幸运的是，在许多情况下，GHC 有许多其他优化可以避免实际创建中间列表单元格（或实际上是基本列表！）。例如，GHC 可以识别 map foo (map bar xs) 等同于 map (foo . bar) xs，它没有中间列表来遍历或分配我们是惰性评估还是热切评估。特别简单的情况，如我使用的示例，将大量内联，并且可能最终编译为直接打印 [4, 8, 12] 而无需分配或评估任何内容。
TLDR: 从某种意义上说，当您链接映射和过滤器等函数时，惰性求值确实避免了重复遍历中间列表。因此，OP 中的引述很可能是准确的（取决于其作者的意图），但存在重要的细微差别，重要的是不要过度推销它。
当需要整个结果时，那些遍历的工作仍然完成；惰性评估只是重新安排工作完成的顺序。如果它允许您大大减少中间结果消耗的内存，这仍然是一个巨大的胜利，因为它们现在可能不必一次全部出现在内存中。
1 请记住，列表的方括号语法只是人类写出一个真正在内存中表示为嵌套系列应用程序的序列的好方法: 构造函数，由 [] 构造函数终止。 [1, 2, 3] 是 1 : (2 : (3 : []))，我们不需要那些内括号，因为 : 构造函数是中缀和右结合的，所以我们可以写成 1 : 2 : 3 : [].