[Haskell-cafe] A challenge

[Thomas Davie]

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.

Bob