[Haskell-cafe] A challenge

Thomas Davie tom.davie at gmail.com
Wed Apr 8 10:57:03 EDT 2009

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.

Can anyone think of a version that combines the benefits of the two?


More information about the Haskell-Cafe mailing list