On Wed, Apr 8, 2009 at 4:57 PM, Thomas Davie <<a href="mailto:tom.davie@gmail.com">tom.davie@gmail.com</a>> wrote:<br>><br>> We have two possible definitions of an "iterateM" function:<br>><br>> iterateM 0 _ _ = return []<br>
> iterateM n f i = (i:) <$> (iterateM (n-1) f =<< f i)<br>><br>> iterateM n f i = sequence . scanl (>>=) (return i) $ replicate n f<br>><br>> The former uses primitive recursion, and I get the feeling it should be better written without it. The latter is quadratic time – it builds up a list of monadic actions, and then runs them each in turn.<br>
><br>> Can anyone think of a version that combines the benefits of the two?<br><br>There seems to be a combinator missing in Control.Monad. Several people have suggested that iterateM should be implemented using a fold. But that seems very unnatural, we're trying to *build* a list, not *consume* it. This suggests that we should use an unfold function instead. Now, I haven't found one in the standard libraries that works for monads but arguably there should be one. So, let's pretend that the following function exists:<br>
<span style="font-family: courier new,monospace;">unfoldM :: Monad m => (b -> m (Maybe(a,b))) -> b -> m [a]</span><br><br>Then the implementation of iterateM becomes more natural:<br><span style="font-family: courier new,monospace;">\begin{code}</span><br>
<span style="font-family: courier new,monospace;">iterateM n f i = unfoldM g (n,i)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> where g (0,i) = return Nothing</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> g (n,i) = do j <- f i</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> return (Just (i,(n-1,j)))</span><br>
<font face="arial,helvetica,sans-serif"><span style="font-family: courier new,monospace;">\end{code}</span><br>I'm not sure whether this version is to your satisfaction but it's quite intuitive IMHO.<br><br>Here's the function I used to test various versions of iterateM:<br>
<span style="font-family: courier new,monospace;">\begin{code}</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">test it = it 4 (\i -> putStrLn (show i) >> return (i+1)) 0</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">\end{code}</span><br><br>Cheers,<br><br>Josef<br></font>