[Haskell-cafe] A challenge
jonathanccast at fastmail.fm
Wed Apr 8 12:44:01 EDT 2009
On Wed, 2009-04-08 at 17:30 +0200, Thomas Davie wrote:
> On 8 Apr 2009, at 17:20, Jonathan Cast wrote:
> > 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
> But this isn't the same function – it only gives back the final
> result, not the intermediaries.
True. Should have read more carefully.
More information about the Haskell-Cafe