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