[Haskell-cafe] How do I do conditional tail recursion in a monad?

DavidA polyomino at f2s.com
Wed Mar 21 05:22:34 EDT 2007


I would like to write a function untilM, which would be to until as mapM is to 

An example use would be if I had a function
dice :: State Int Int
which returns random dice throws within a state monad.

Then I'd like to be able to do something like
untilM (\(s,p)-> s>=100) f (0,1)
    where f (s,p) = do d <- dice
                       return (s+d, p*d)
This should throw dice until the sum exceeds 100, and keeping track of the 
product as we go along.

The problem is that I get stuck trying to manage the interaction of the 
conditional and the recursion in untilM. Let's start with until:
until p f x = if p x then x else until p f (f x)

So I figure untilM should look something like:
untilM :: Monad m => (a -> Bool) -> (a -> m a) -> a -> m a
untilM p f x = return (if p x then x else untilM p f (f x))
The problem is that the two branches of the conditional have different types. 
If I try to remedy that by changing "then x" to "then return x", it still isn't 

(My real question is, how do I do conditional tail recursion in a monad?)

Thanks in advance.

More information about the Haskell-Cafe mailing list