[Haskell-cafe] Short-circuiting a fold

[Kurt Hutchinson]

Here's a bit of Thursday afternoon fun.

Mission:
Define "ssfold," a short-circuiting fold. It evaluates to the "folded
value" that first satisfies the given predicate.
> ssfold :: ( a -> Bool ) -> ( a -> b -> a ) -> a -> [b] -> a

Here are two of mine.

Straightforward:
> ssfold p f z = head . dropWhile ( not . p ) . scanl f z

Monadic:
> data Done a b = Done { undone :: a } | NotDone b
> instance Monad ( Done a ) where
>     ( NotDone i ) >>= f = f i
>     ( Done    r ) >>= _ = Done r
>     return = NotDone
>
> ssfold p f z = undone . foldM (\ v e -> if p v then Done v else NotDone ( f v e ) ) z

I want to see some real creativity here, so pull out all the stops.

Kurt