haskell - 在 Haskell 中只想要一个答案

Question

当我只想要一个答案时，如何让 fold{l,r} 终止？

假设我有一个 bool 值 b1,b2,b3,... 的列表，我想对它们进行 OR 运算。如何弃牌以在第一个真值处停止？

Answer 1

它已经做到了!作为一个例子，让我们列一个 list

foo :: [Bool]
foo = [False, False, False, True] ++ repeat False

repeat 只是生成一个无限列表，如果我们将其加载到 GHCi 中

*Main> foldr (||) False foo
  True

“但是，但是怎么办？”你可能想知道，Haskell 是懒惰的，foldr 也是。如果你看一下实现，你会注意到它创建了这样的东西

 foldr f a [b, c, d, e ... z] == (b `f` (c `f` (... (z `f` a)..)))

请注意，当您评估它时，如果 f 不需要右侧，则不会对其进行评估，我们可以忽略整个列表的其余部分，即使它是无限的。这在像 Haskell 这样的惰性语言中是可能的，因为我们只在需要时才评估事物。

在 || 的情况下，因为它被定义为

True  || _ = True
False || a = a

当左侧为真时，我们停止评估列表。免费短路!

请注意，foldl 不共享这个不错的属性，因为它涉及列表的所有元素。这导致了一个很好的经验法则，如果你想要短路/非严格性，foldr 通常是正确的选择，否则 foldl' 可能更快。