[Haskell-cafe] folds with escapes

[Stefan O'Rear]

On Wed, Jul 04, 2007 at 04:20:20PM -0700, Michael Vanier wrote:
> I'm sure this has been done a hundred times before, but a simple 
> generalization of foldl just occurred to me and I wonder if there's 
> anything like it in the standard libraries (I couldn't find anything).
> Basically, I was trying to define the "any" function in terms of a fold, 
> and my first try was this:
>
> > any :: (a -> Bool) -> [a] -> Bool
> > any p = foldl (\b x -> b || p x) False
>
> This is inefficient, because if (p x) is ever True the rest of the list is 
> scanned unnecessarily.

Rather than create a new escape fold, it's much easier, simpler, and
faster just to use a right fold:

any p = foldr (\x b -> p x || b) False

That will short-ciruit well by laziness, and is made tailrecursive by
same.

Stefan