On 8 Apr 2009, at 18:21, Claus Reinke wrote:
|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
These function are not the same (sequence of scanl? try using print in f). Also, I seriously hope you are not looking for this line noise:-)
No indeed – that's what I meant about the latter being quadratic – it runs the action far more times than the other.
iterateM' = (foldr op (const $ return []) .) . replicate where f `op` x = uncurry (<$>) . ((:) &&& ((x =<<) . f))
Because if you do, your penance for using it would involve demonstrating that this is equivalent (+-1), or not (and do not mention my name anywhere near it!-)
ghci tells me this: Prelude Control.Applicative Control.Arrow> let iterateM' = let f `op` x = uncurry (<$>) . ((:) &&& ((x=<<) . f)) in (foldr op (const $ return []) .) . replicate <interactive>:1:92: Ambiguous type variable `m' in the constraints: `Monad m' arising from a use of `return' at <interactive>: 1:92-100 `Functor m' arising from a use of `op' at <interactive>:1:80-81 Probable fix: add a type signature that fixes these type variable(s)