<div><span class="gmail_quote">On 12/20/07, <b class="gmail_sendername">Joost Behrends</b> &lt;<a href="mailto:webmaster@h-labahn.de">webmaster@h-labahn.de</a>&gt; wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">The syntax with the block in<br><br>&quot;newtype State s a = State { runState :: s -&gt; (a,s) }&quot;<br>
<br>is not in the tutorials i read.</blockquote>
<div>&nbsp;</div>
<div>newtype creates a new type which is treated exactly the same as an existing type at runtime, but which is distinct to the typechecker.</div>
<div>&nbsp;</div>
<div>For example, this code:</div>
<div>&gt; newtype X = MkX [Int]</div>
<div>&gt; -- MkX :: [Int] -&gt; X</div>
<div>&gt; unX :: X -&gt; [Int]</div>
<div>&gt; unX (MkX&nbsp;val) = val</div>
<div>&nbsp;</div>
<div>Now, you cannot call &quot;sum (MkX [1,2,3])&quot; because sum takes a list and you&#39;re passing an &quot;X&quot;.&nbsp; But you can call &quot;sum (unX (MkX [1,2,3]))&quot;.&nbsp; Since this is a newtype, the work done in &quot;unX&quot; and &quot;MkX&quot; is entirely erased at runtime; no allocation or pointer-following takes place.
</div>
<div>&nbsp;</div>
<div>The syntax given is slightly more complicated:</div>
<div>&nbsp;</div>
<div>&gt; newtype State s a = State { runState :: s -&gt; (a,s) }</div>
<div>&nbsp;</div>
<div>This is using the &quot;record&quot; syntax for data constructors, but it&#39;s basically the same as the following:</div>
<div>&nbsp;</div>
<div>&gt; newtype State s a = State (s -&gt; (a,s))</div>
<div>&gt; runState (State f) = f</div>
<div>&nbsp;</div>
<div>So, runState is just unwrapping the function from the newtype.&nbsp; Since this is a newtype, there&#39;s no actual pointer traversal taking place; the distinction is only made during typechecking.</div>
<div>&nbsp;</div>
<div>The following two functions should compile to exactly the same machine code:</div>
<div>&nbsp;</div>
<div>
<div>&gt;&nbsp;test1 :: Int -&gt; ((), Int)</div>
<div>&gt; test1 = \x -&gt;&nbsp;((), x+1)</div>
<div>&nbsp;</div></div>
<div>&gt; test2 ::&nbsp;Int -&gt; ((), Int)</div>
<div>&gt; test2 = runState (State (\x -&gt;&nbsp;((), x+1)))</div>
<div>&nbsp;</div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"> And i do not understand<br>&quot; ... passed the DivIter directly along &quot;. &quot;Passed along&quot; ??
</blockquote>
<div>&nbsp;</div>
<div>Recall your original code:</div>
<div>&nbsp;</div>
<div>&gt; divisions :: State DivIter DivIter</div>
<div>&gt; divisions = do<br>&gt; &nbsp; &nbsp;y &lt;- get<br>&gt; &nbsp; &nbsp;if divisor y &lt;= bound y then do<br>&gt; &nbsp; &nbsp; &nbsp; &nbsp;put ( divstep y )<br>&gt; &nbsp; &nbsp; &nbsp; &nbsp;divisions<br>&gt; &nbsp; &nbsp; &nbsp; &nbsp;else<br>&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return y<br>&nbsp;</div>
<div>Lets de-sugar that:</div>
<div>&nbsp;</div>
<div>&gt; divisions = get &gt;&gt;= \y -&gt; </div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp; if divisor y &lt;= bound y</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then (put (divstep y) &gt;&gt; divisions)</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else return y</div>
<div>&nbsp;</div>
<div>Inlining get, put, and return:</div>
<div>&nbsp;</div>
<div>&gt; divisions = (State (\s -&gt; (s,s))) &gt;&gt;= \y -&gt;</div>
<div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp; if divisor y &lt;= bound y</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then (State (\s -&gt; ((), divstep y)) &gt;&gt; divisions)</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else State (\s -&gt; (y, s))</div>
<div>&nbsp;</div>
<div>After inlining (&gt;&gt;=) and (&gt;&gt;), and running a few simplification passes (in particular, runState (State x) = x, and beta-reduction), you end up with this:</div>
<div>&nbsp;</div>
<div>&gt; divisions = State (\y -&gt; </div>
<div>&gt;&nbsp;&nbsp;&nbsp; if divisor y &lt;= bound y</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then runState divisions (divstep y)</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else (y,y))</div>
<div>&nbsp;</div>
<div>You can remove the State monad from this pretty trivially:</div>
<div>&nbsp;</div>
<div>&gt; divisions :: DivIter -&gt; (DivIter, DivIter)</div>
<div>&gt; divisions y =</div>
<div>&gt;&nbsp;&nbsp;&nbsp; if divisor y &lt;= bound y</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then divisions (divstep y)</div>
<div>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else (y,y)</div>
<div>&nbsp;</div>
<div>or,</div>
<div>&nbsp;</div>
<div>&gt; divisions y</div>
<div>&gt;&nbsp;&nbsp; |&nbsp;divisor y &lt;= bound y = divisions (divstep y)</div>
<div>&gt;&nbsp;&nbsp;&nbsp;| otherwise&nbsp;= (y,y)</div>
<div>&nbsp;</div>
<div>This&nbsp;version of&nbsp;the&nbsp;code&nbsp;threads the &quot;DivIter&quot; state manually through each call, but it&#39;s exactly the same as what the State version is doing.&nbsp; No destructive updates anywhere to be seen!</div>
<div>&nbsp;</div>
<div>&nbsp; -- ryan</div></div></div>