[Haskell-beginners] Iterating a monadic action with memoization

[Brent Yorgey]

On Mon, Aug 15, 2011 at 09:00:19AM +0100, Tim Cowlishaw wrote:
> Hi all,
> 
> I was wondering if any of you knew whether the following was possible,
> (I discussed this a little on #haskell at the weekend but didn't quite
> get to the bottom of it):
> 
> Say I have a monadic action:
> 
> > f :: a -> m a
> 
> and an initial value of type a.
> 
> I'd like to iterate this action and collect the results of each
> iteration in a list, as with 'iterate' on normal functions:
> 
> > iterate (>>= f) . return $ a
> 
> However, I would also like to memoize the intermediate results of the
> iteration, such that the entire iteration runs in O(n) time rather
> than O(n^2). This also implies a slight semantic difference, as
> side-effecting or non-deterministic actions will not be repeated in
> each iteration, while maintaining the laziness of the iteration
> function. Is it possible to do this?

How about this?

  iterateM :: Monad m => (a -> m a) -> a -> m [a]
  iterateM f a = (a:) `liftM` (f a >>= iterateM f)

-Brent