[Haskell-cafe] How do I do conditional tail recursion in a monad?
Jules Bean
jules at jellybean.co.uk
Wed Mar 21 05:31:26 EDT 2007
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
More information about the Haskell-Cafe
mailing list