# [Haskell-cafe] Re: folds with escapes

Logan Capaldo logancapaldo at gmail.com
Thu Jul 5 20:20:39 EDT 2007

```Michael Vanier <mvanier <at> cs.caltech.edu> writes:

>
> 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
>
>  > 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.
> So I wrote a more general foldl with an "escape" predicate which terminates
the evaluation, along
> with a function which tells what to return in that case (given an argument of
the running total 'z'):
>
>  > foldle :: (b -> Bool) -> (a -> a) -> (a -> b -> a) -> a -> [b] -> a
>  > foldle _ _ _ z [] = z
>  > foldle p h f z (x:xs) = if p x then h z else foldle p h f (f z x) xs
>
> Using this function, "foldl" is:
>
>  > foldl' = foldle (const False) id
>
> and "any" is just:
>
>  > any p = foldle p (const True) const False
>

There have already been better responses / solutions to this,
but I just wanted to point out that there was already a
form of an "escaping" left fold, namely foldM.

> import Data.Maybe ( isJust )
> import Control.Monad ( foldM )

> any p = not . isJust . foldM (\_ x -> if p x then Nothing
>                                          else Just ()) ()

Of course the logic is a little confusing to read :)

```