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
