[Haskell-cafe] A challenge
Jonathan Cast
jonathanccast at fastmail.fm
Wed Apr 8 11:20:20 EDT 2009
On Wed, 2009-04-08 at 16:57 +0200, Thomas Davie wrote:
> We have two possible definitions of an "iterateM" function:
>
> iterateM 0 _ _ = return []
> iterateM n f i = (i:) <$> (iterateM (n-1) f =<< f i)
>
> iterateM n f i = sequence . scanl (>>=) (return i) $ replicate n f
>
> The former uses primitive recursion, and I get the feeling it should
> be better written without it. The latter is quadratic time – it
> builds up a list of monadic actions, and then runs them each in turn.
It's also quadratic in invocations of f, no? If your monad's (>>=)
doesn't object to being left-associated (which is *not* the case for
free monads), then I think
iterateM n f i = foldl (>>=) (return i) $ replicate n f
would be both correct and linear. If you're monad's (>>=) is itsef
quadratic in time when left-associated, you can try applying a CPS
transformation to fix the problem.[1]
jcc
[1] http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf
More information about the Haskell-Cafe
mailing list