只想在Haskell中找到一个答案

Question

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

假设我有一个布尔值列表b1,b2,b3,...我希望将它们全部组合在一起.如何让折叠停止在第一个真值上？

Answer 1

它已经做到了!举个例子,让我们列一个清单

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'可能更快.