Only want one answer in Haskell

Question

How do I make fold{l,r} terminate when I only want one answer?

Suppose I have a list of booleans b1,b2,b3,... and I want to OR all of them together. How do I get fold to stop on the first true value?

Answer 1

It already does! As an example let's make a list

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

where repeat just makes an infinite list, and if we load this into GHCi

*Main> foldr (||) False foo
  True

"But, but how?" you might wonder, well Haskell is lazy and so is foldr. If you look at the implementation, you'll notice that it creates something like this

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

Notice that when you evaluate it, if f doesn't need that right side, it won't be evaluated and we could ignore the whole rest of the list, even if it's infinite. This is possible in a lazy language like Haskell because we only evaluate things when they're needed.

In the case of || since it's defined as

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

when the left side is true, we stop evaluating the list. Short circuiting for free!

Note, foldl doesn't share this nice property since it touches all elements of the list. This leads to a nice rule of thumb, if you want short circuiting/nonstrictness, foldr is usually the right choice, otherwise foldl' is probably faster.