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 > 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. > 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 :) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe