<div class="gmail_quote">On Thu, Jan 1, 2009 at 12:25 PM, Brian Hurt <span dir="ltr">&lt;<a href="mailto:bhurt@spnz.org">bhurt@spnz.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
First off, let me apologize for this ongoing series of stupid newbie questions. &nbsp;Haskell just recently went from that theoretically interesting language I really need to learn some day to a language I actually kinda understand and can write real code in (thanks to Real World Haskell). &nbsp;Of course, this gives rise to a whole bunch of &quot;wait- why is it this way?&quot; sort of questions.<br>

<br>
So today&#39;s question is: why isn&#39;t there a Strict monad? &nbsp;Something like:<br>
<br>
data Strict a = X a<br>
<br>
instance Monad Strict where<br>
 &nbsp; &nbsp;( &gt;&gt;= ) (X m) f = let x = f m in x `seq` (X x)<br>
 &nbsp; &nbsp;return a = a `seq` (X a)</blockquote><div><br></div><div>First, the error is: &nbsp;f :: a -&gt; Strict b, so you have to unpack the result first.</div><div><br></div><div>&nbsp;&nbsp;<span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">X m &gt;&gt;= f = let X x = f m in x `seq` X x</span></div>
<div><br></div><div>Now I would like to take a moment to point out something that is a cause of much fuzziness and confusion when talking about strictness. &nbsp;(1) &nbsp;&quot;f is strict&quot; means <span class="Apple-style-span" style="font-style: italic;">exactly </span>f _|_ = _|_. &nbsp;(2) &quot;x `seq` y&quot; means _|_ when x is _|_, y otherwise. &nbsp;These are precise, mathematical definitions. &nbsp;Use them instead of your intuition to start with, until you fix your intuition.</div>
<div><br></div><div>Now consider the right neutral monad law:<br></div><div><br></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&nbsp;m &gt;&gt;= return = m</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br>
</span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">This fails when m = X _|_:</span></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><br>
</span></div><div><span class="Apple-style-span" style="font-size: 12px;">&nbsp;<span class="Apple-style-span" style="font-family: &#39;courier new&#39;;">X _|_ &gt;&gt;= return =&nbsp;</span></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><span class="Apple-style-span" style="font-family: &#39;courier new&#39;;">let X x = return _|_ in x `seq` X x =</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">let X x = _|_ `seq` X _|_ in x `seq` X x =</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">let X x = _|_ in x `seq` X x = _|_</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">Because X _|_ is not _|_.</span></span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;">The problem here was that return was too strict; i.e. return _|_ was _|_ instead of X _|_. &nbsp;So let&#39;s relax return to &quot;return = X&quot;, and then see how it goes:</span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><span class="Apple-style-span" style="font-size: 13px; "><div><span class="Apple-style-span" style="font-size: 12px; ">&nbsp;<span class="Apple-style-span" style="font-family: &#39;courier new&#39;; ">X _|_ &gt;&gt;= return =&nbsp;</span></span></div>
<div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; ">let X x = return _|_ in x `seq` X x =</span></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">let X x = X _|_ in x `seq` X x =</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">_|_ `seq` X _|_ = _|_</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br>
</span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">Whoops! &nbsp;It happened again. &nbsp;So we&#39;re forced to relax the definition of bind also. &nbsp;And then the monad isn&#39;t strict as we were attempting. &nbsp;Maybe the problem is somewhere else: that X _|_ and _|_ are different; let&#39;s fix that by making Strict a newtype:</span></span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">newtype Strict a = X a</span></span></div>
<div><br></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">instance Monad Strict where</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">&nbsp;&nbsp; &nbsp;X m &gt;&gt;= f = let X x = f m in x `seq` X x</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">&nbsp;&nbsp; &nbsp;return x = x `seq` X x</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br>
</span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">Okay, first let&#39;s prove a little lemma to show the absurdity of this definition :-) :</span></span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">Let f x = x `seq` X x, then f = X.</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;">Let&#39;s consider two cases:&nbsp;</span></div><div>
<span class="Apple-style-span" style="font-size: 12px;">(1) x is not _|_: then f x = x `seq` X x.&nbsp;&nbsp;But the definition of seq is that seq x y is _|_ when x is _|_, and y otherwise. &nbsp;So in this case f x = X x.</span></div><div>
<span class="Apple-style-span" style="font-size: 12px;">(2) x is _|_: then f _|_ = _|_ `seq` X _|_ = _|_. &nbsp;But X _|_ = _|_ because of the semantics of newtypes, so f x = X x here also.</span></div><div><span class="Apple-style-span" style="font-size: 12px;">Qed.</span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;">So now we know we can replace x `seq` X x with simply X x without changing semantics:</span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><span class="Apple-style-span" style="font-size: 13px; "><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">instance Monad Strict where</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">&nbsp;&nbsp; &nbsp;X m &gt;&gt;= f = let X x = f m in X x</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">&nbsp;&nbsp; &nbsp;return x = X x</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">And performing some obvious rewrites:</span></span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px;"><span class="Apple-style-span" style="font-size: 13px; "><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">instance Monad Strict where</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">&nbsp;&nbsp; &nbsp;X m &gt;&gt;= f = f m</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px; ">&nbsp;&nbsp; &nbsp;return = X</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br></span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">And there you have your Strict monad. &nbsp;Oh, but it&#39;s the same as Identity. &nbsp;:-)</span></span></div>
<div><span class="Apple-style-span" style="font-size: 12px;"><br></span></div><div>So that&#39;s the answer: there already is a Strict monad. &nbsp;And an attempt to make a lazier one strict just results in breaking the monad laws.</div>
<div><br></div><div>There&#39;s another answer though, regarding your question for why we don&#39;t just use StrictT State instead of a separate State.Strict. &nbsp;This message is already too long, and I suspect this will be the popular reply anyway, but the short answer is that Strict State is called that because it is strict in its <span class="Apple-style-span" style="font-style: italic;">state</span>, not in its value. StrictT wouldn&#39;t be able to see that there even is a state, so it wouldn&#39;t be able to change semantics. And as we saw, an attempt to be overly strict in your value just results in law breaking.</div>
<div><br></div><div>Luke</div></span></span></div></span></span></div></span></span></div></div>