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
I also thought of an even more general fold:
> foldle' :: (b -> Bool) -> (a -> b -> [b] -> a) -> (a -> b -> a) -> a -> [b]
-> a
> foldle' _ _ _ z [] = z
> foldle' p h f z (x:xs) = if p x then h z x xs else foldle' p h f (f z x) xs
Using this definition, you can write "dropWhile" as:
> dropWhile :: (a -> Bool) -> [a] -> [a]
> dropWhile p = foldle' (not . p) (\_ x xs -> x:xs) const []
Again, I'm sure this has been done before (and no doubt better); I'd appreciate any pointers to
previous work along these lines.
Mike
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
