Avoiding explicit recursion in Haskell
- by Travis Brown
The following simple function applies a given monadic function iteratively until it hits a Nothing, at which point it returns the last non-Nothing value. It does what I need, and I understand how it works.
lastJustM :: (Monad m) => (a -> m (Maybe a)) -> a -> m a
lastJustM g x = g x >>= maybe (return x) (lastJustM g)
As part of my self-education in Haskell I'm trying to avoid explicit recursion (or at least understand how to) whenever I can. It seems like there should be a simple non-explicitly recursive solution in this case, but I'm having trouble figuring it out.
I don't want something like a monadic version of takeWhile, since it could be expensive to collect all the pre-Nothing values, and I don't care about them anyway.
I checked Hoogle for the signature and nothing shows up. The m (Maybe a) bit makes me think a monad transformer might be useful here, but I don't really have the intuitions I'd need to come up with the details (yet).
It's probably either embarrassingly easy to do this or embarrassingly easy to see why it can't or shouldn't be done, but this wouldn't be the first time I've used self-embarrassment as a pedagogical strategy.
Background: Here's a simplified working example for context: suppose we're interested in random walks in the unit square, but we only care about points of exit. We have the following step function:
randomStep :: (Floating a, Ord a, Random a) =>
a -> (a, a) -> State StdGen (Maybe (a, a))
randomStep s (x, y) = do
(a, gen') <- randomR (0, 2 * pi) <$> get
put gen'
let (x', y') = (x + s * cos a, y + s * sin a)
if x' < 0 || x' > 1 || y' < 0 || y' > 1
then return Nothing
else return $ Just (x', y')
Something like evalState (lastJustM (randomStep 0.01) (0.5, 0.5)) <$> newStdGen will give us a new data point.
