<br><div class="gmail_quote">On Wed, Apr 8, 2009 at 7:11 PM, Thomas Davie <span dir="ltr">&lt;<a href="mailto:tom.davie@gmail.com">tom.davie@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="im"><br>
On 8 Apr 2009, at 19:05, Josef Svenningsson wrote:<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On Wed, Apr 8, 2009 at 4:57 PM, Thomas Davie &lt;<a href="mailto:tom.davie@gmail.com" target="_blank">tom.davie@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt; We have two possible definitions of an &quot;iterateM&quot; function:<br>
&gt;<br>
&gt; iterateM 0 _ _ = return []<br>
&gt; iterateM n f i = (i:) &lt;$&gt; (iterateM (n-1) f =&lt;&lt; f i)<br>
&gt;<br>
&gt; iterateM n f i = sequence . scanl (&gt;&gt;=) (return i) $ replicate n f<br>
&gt;<br>
&gt; 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>
&gt;<br>
&gt; 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&#39;re trying to *build* a list, not *consume* it. This suggests that we should use an unfold function instead. Now, I haven&#39;t found one in the standard libraries that works for monads but arguably there should be one. So, let&#39;s pretend that the following function exists:<br>

unfoldM :: Monad m =&gt; (b -&gt; m (Maybe(a,b))) -&gt; b -&gt; m [a]<br>
<br>
Then the implementation of iterateM becomes more natural:<br>
\begin{code}<br>
iterateM n f i = unfoldM g (n,i)<br>
 where g (0,i) = return Nothing<br>
       g (n,i) = do j &lt;- f i<br>
                    return (Just (i,(n-1,j)))<br>
\end{code}<br>
I&#39;m not sure whether this version is to your satisfaction but it&#39;s quite intuitive IMHO.<br>
</blockquote>
<br></div>
That one certainly seems very natural to me, now if only unfoldM existed :)<br>
<br>
</blockquote></div>Well, you can always write it yourself, but that might be a little excessive if you only want it for iterateM. The other option is of course to make a library proposal. The thing is, most people never use unfolds so I don&#39;t know how likely it is to be included.<br>
<br>Cheers,<br><br>Josef<br>