[Haskell-beginners] Iterating a monadic action with memoization

[Tim Cowlishaw]

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?

Many thanks,

Tim