<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<div><font face="Inconsolata" style="font-size: 14px;" class="">Hi Li-yao,</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div>
<div><font face="Inconsolata" class=""><span style="font-size: 14px;" class="">Thanks for you interesting thoughts.</span></font></div>
<div class=""><br class="">
</div>
</div>
<div>
<blockquote type="cite" class=""><font face="Inconsolata" style="font-size: 14px;" class="">There is also an opposite situation, where evaluating the second argument allows us to free a lot of memory, as that argument would otherwise remain a thunk with references
to many things.<br class="">
</font></blockquote>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">Good point, but this is one of the tradeoffs with laziness. In the case of GHC, will the runtime not eventually free the memory of the second argument and everything it points to? It surely must
do this one way or another since otherwise laziness would mean that while a process is running it will keep leaking space.</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div>
<blockquote type="cite" class=""><font face="Inconsolata" style="font-size: 14px;" class="">But to compare two pairs `(a,b) <= (x,y)` we would have to first traverse `(a,b)` to decide whether it's the smallest element, before evaluating the second argument
to WHNF and comparing component-wise. Besides the extra complexity (both in code and in run time), this would not be less strict than the current default, since the first argument could get completely evaluated before even looking at the second one: `(False,
_|_) <= (True, True) = _|_` (currently, this is `True`).</font></blockquote>
</div>
<div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">So with the laziest possible implementation (below—do check for accuracy, I might have missed something) these are the cases where the result is defined for Bool and undefined for Lazy Bool:</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div>
<div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(F,u) <= (T,F)</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(F,u) <= (T,T)</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(F,u) <= (T,u)</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">vs. (undefined for Bool and defined for Lazy Bool)</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">
<div>(F,F) <= (F,u)</div>
<div>(F,F) <= (u,F)</div>
<div>(F,F) <= (u,T)</div>
<div>(F,F) <= (u,u)</div>
<div>(T,F) <= (T,u)</div>
<div><br class="">
</div>
<div>So it does seem that we can make it marginally more lazy overall. I’m not saying we should, I was just genuinely surprised that Ord is strict.</div>
</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">Definitions:</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
</div>
</div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">F <= _ = T</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">T <= q = q</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">F < q = q</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">T < _ = F</font></div>
</div>
<div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(p, q) == (r, s) = p == r /\ q == s</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(F, F) <= _ = T</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(p, q) <= (r, s) = p < r \/ p == r /\ q <= s</font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class="">(T, T) < _ = F</font></div>
<div class=""><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
</div>
</div>
<div>
<blockquote type="cite" class=""><font face="Inconsolata" style="font-size: 14px;" class="">We also would not know whether the type (a, b) has a smallest element without stronger constraints than (Ord a, Ord b), so this optimization is really only practically
feasible for types with a nullary first constructor.</font></blockquote>
<font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<div><font face="Inconsolata" class=""><span style="font-size: 14px;" class="">Hm, perhaps we are thinking about this in different ways. From the definition above, we don’t need any stronger constraints than Ord.</span></font></div>
<div><font face="Inconsolata" class=""><span style="font-size: 14px;" class=""><br class="">
</span></font></div>
<div><font face="Inconsolata" class=""><span style="font-size: 14px;" class="">Best,</span></font></div>
<div><font face="Inconsolata" class=""><span style="font-size: 14px;" class=""><br class="">
</span></font></div>
<div><font face="Inconsolata" class=""><span style="font-size: 14px;" class="">Vilem</span></font></div>
<div><font face="Inconsolata" style="font-size: 14px;" class=""><br class="">
</font></div>
<blockquote type="cite" class="">
<div class=""><font face="Inconsolata" style="font-size: 14px;" class="">On 2 Jan 2019, at 15:06, Li-yao Xia <<a href="mailto:lysxia@gmail.com" class="">lysxia@gmail.com</a>> wrote:</font></div>
<font face="Inconsolata" style="font-size: 14px;" class=""><br class="Apple-interchange-newline">
</font>
<div class="">
<div class=""><font face="Inconsolata" style="font-size: 14px;" class="">Hi Vilem,<br class="">
<br class="">
> This is not just about crashing. (I’m using `undefined` as a way of<br class="">
> making strictness explicit.) `False >= veryExpensiveComputation`<br class="">
> should return `True` immediately without any unnecessary computation.<br class="">
<br class="">
There is also an opposite situation, where evaluating the second argument allows us to free a lot of memory, as that argument would otherwise remain a thunk with references to many things.<br class="">
<br class="">
> Also it doesn’t seem like a special case: this makes sense for any partially ordered Type with a top and/or bottom element.<br class="">
<br class="">
That may be acceptable with Bool because its values are small. But to compare two pairs `(a,b) <= (x,y)` we would have to first traverse `(a,b)` to decide whether it's the smallest element, before evaluating the second argument to WHNF and comparing component-wise.
Besides the extra complexity (both in code and in run time), this would not be less strict than the current default, since the first argument could get completely evaluated before even looking at the second one: `(False, _|_) <= (True, True) = _|_` (currently,
this is `True`). We also would not know whether the type (a, b) has a smallest element without stronger constraints than (Ord a, Ord b), so this optimization is really only practically feasible for types with a nullary first constructor.<br class="">
<br class="">
Li-yao<br class="">
</font></div>
</div>
</blockquote>
</div>
<br class="">
</div>
</body>
</html>