Well okay, I don&#39;t really need the state since it is already in the list... So cleaned up<div><br></div><div><div><div><div><div>iterateM n i = </div><div>  fmap (tail . reverse) .</div><div>  foldM collectEffect [i] .</div>
<div>  replicate n</div><div>  where</div><div>    collectEffect xxs@(x:xs) f = fmap (:xxs) (f x)</div><div><br></div></div></div><div>But I&#39;m sure it can be much simpler (I don&#39;t understand Claus&#39; version :-)</div>
<div><br></div><div class="gmail_quote">On Wed, Apr 8, 2009 at 6:38 PM, Peter Verswyvelen <span dir="ltr">&lt;<a href="mailto:bugfact@gmail.com">bugfact@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Oh, I could have written it in more point free style (with arguments reversed) as<div><br></div><div><div>iterateM n i = fmap (reverse . snd) . </div><div class="im"><div>               foldM collectEffect (i,[]) .</div><div>
               replicate n</div>
</div><div class="im"><div>  where</div><div>    collectEffect (x,rs) f = f x &gt;&gt;= \y -&gt; return (y,y:rs)</div><div><br></div></div><div>and I&#39;m sure collectEffect could also be improved, but I&#39;m still in newbieeee land</div>
<div><div></div><div class="h5"><div><br>
</div><div class="gmail_quote">On Wed, Apr 8, 2009 at 6:33 PM, Peter Verswyvelen <span dir="ltr">&lt;<a href="mailto:bugfact@gmail.com" target="_blank">bugfact@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

I don&#39;t think scanl can work here, since the monadic action has to be applied to the result of previous one and will have a side effect, so if you build a list like<div><br></div><div>[return i, return i &gt;&gt;= f, return i &gt;&gt;= f &gt;&gt;= f, ...]</div>


<div><br></div><div>the first action will do nothing, the second action will have a single side effect, but the third one will have 3 side effects instead of 2, because it operates on the side-effect performed by the second one.</div>


<div><br></div><div>This seems to work (a combination of manual state monad and foldM, I could also have used a state monad transformer I guess)</div><div><br></div><div><div><div>iterateM n f i = foldM collectEffect (i,[]) (replicate n f) &gt;&gt;= return . reverse . snd</div>


<div>  where</div><div>    collectEffect (x,rs) f = f x &gt;&gt;= \y -&gt; return (y,y:rs)</div><div><br></div><div>Ugly test:</div><div><div><br></div><div>var = unsafePerformIO $ newIORef 0</div><div><br></div><div>inc i = do</div>


<div><span style="white-space:pre">        </span>x &lt;- readIORef var</div><div><span style="white-space:pre">        </span>let y = x+i</div><div><span style="white-space:pre">        </span>writeIORef var y</div>
<div><span style="white-space:pre">        </span>return y</div><div><br></div><div>results in</div><div><br></div><div><div>*Main&gt; iterateM 10 inc 1</div><div>[1,2,4,8,16,32,64,128,256,512]</div><div>*Main&gt; iterateM 10 inc 1</div>


<div>[513,1026,2052,4104,8208,16416,32832,65664,131328,262656]</div><div><br></div><div>but maybe this is not what you&#39;re looking for?</div><div><br></div></div><div><br></div></div><div><br></div><div><br></div></div>


<div><br></div></div><div><div></div><div><div><br></div><div><br></div><div><br><div class="gmail_quote">On Wed, Apr 8, 2009 at 5:30 PM, Thomas Davie <span dir="ltr">&lt;<a href="mailto:tom.davie@gmail.com" target="_blank">tom.davie@gmail.com</a>&gt;</span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><br>
On 8 Apr 2009, at 17:20, Jonathan Cast wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On Wed, 2009-04-08 at 16:57 +0200, Thomas Davie wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
We have two possible definitions of an &quot;iterateM&quot; function:<br>
<br>
iterateM 0 _ _ = return []<br>
iterateM n f i = (i:) &lt;$&gt; (iterateM (n-1) f =&lt;&lt; f i)<br>
<br>
iterateM n f i = sequence . scanl (&gt;&gt;=) (return i) $ replicate n f<br>
<br>
The former uses primitive recursion, and I get the feeling it should<br>
be better written without it.  The latter is quadratic time – it<br>
builds up a list of monadic actions, and then runs them each in turn.<br>
</blockquote>
<br>
It&#39;s also quadratic in invocations of f, no?  If your monad&#39;s (&gt;&gt;=)<br>
doesn&#39;t object to being left-associated (which is *not* the case for<br>
free monads), then I think<br>
<br>
iterateM n f i = foldl (&gt;&gt;=) (return i) $ replicate n f<br>
</blockquote>
<br></div>
But this isn&#39;t the same function – it only gives back the final result, not the intermediaries.<br>
<br>
Bob_______________________________________________<div><div></div><div><br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div></div></div>
</blockquote></div><br></div></div>