[Haskell-cafe] folds with escapes

Michael Vanier mvanier at cs.caltech.edu
Wed Jul 4 20:08:01 EDT 2007

That's cool -- good point.  takeWhile is also trivially defined in terms of foldr:

 > takeWhile p = foldr (\x r -> if p x then x:r else []) []

Can you do dropWhile in terms of foldr?  I don't see how.


Stefan O'Rear wrote:
> 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

More information about the Haskell-Cafe mailing list