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