DavidA wrote:
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 happy.
You are applying return to the result of untilM. This makes a m (m a). The following is closer: *Main> :t let untilM p f x = if p x then return x else untilM p f (f x) in untilM let untilM p f x = if p x then return x else untilM p f (f x) in untilM :: (Monad m) => (a -> Bool) -> (a -> a) -> a -> m a ...but here 'f' is a pure function, not a monadic action. If you want f to be a monadic action then you want: *Main> :t let untilM p f x = if p x then return x else untilM p f =<< f x in untilM let untilM p f x = if p x then return x else untilM p f =<< f x in untilM :: (Monad m) => (a -> Bool) -> (a -> m a) -> a -> m a (if you prefer do notation to explicit binds, rewrite "untilM p f =<< f x" as "y <- f x ; untilM p f y")
(My real question is, how do I do conditional tail recursion in a monad?)
actually I don't think that was your real question :) Your real question was about conditional recursion in monads, but had nothing to do with tailness or otherwise. Tail recursion is a concept which has implementation relevance in an eager language, but is often a red-herring in a lazy language. Jules