<div>Greetings,</div><div><br></div><div>It might be nice to have &quot;nubBy&quot; work in a way that is more intuitive to computer scientists who expect list evaluation to work in a specific order. Unfortunately, Haskell is quite explicit about not specifying the order of evaluation, which can make Haskell more intuitive for mathematicians, and less intuitive for most other people.</div>
<div><br></div><div>I don&#39;t work on GHC or on the Haskell language committee, but my understanding is that making the &quot;nubBy&quot; function undefined for operations that do not test for equality is a simplifying assumption that allows more freedom for evaluation and optimization. Here is an overly-simple example, but I hope it makes sense:</div>
<div><br></div><div>a = nubBy (==) ([10-5] ++ takeWhile (&lt;5) [0..20])</div><div>b = nubBy (==) (nubBy (==) [5] ++ takeWhile (&lt;5) (nubBy (==) [0..20]))</div><div><br></div><div>According to Haskell, both &#39;a&#39; and &#39;b&#39; are mathematically equivalent, because &quot;nubBy&quot; is a distributive and associative function. This implies that if the compiler can somehow produce more efficient code by first converting &#39;a&#39; into &#39;b&#39; and then applying optimization, it should have the freedom to do so, and laziness guarantees that freedom. This is a poor example because obviously &#39;b&#39; couldn&#39;t possibly be easier to optimize than &#39;a&#39;. But really, who can fathom the logic of those crazy programmers who implemented the compiler with their ridiculous (but somehow always optimal) optimization strategies?</div>
<div><br></div><div>If you require interpretation to go by list order, then you also must eliminate the distributive and associative properties of the &quot;nubBy&quot; function. By declaring &quot;nubBy&quot; only work on equality operations, you guarantee that it is associative and distributive across lists, and this allows a host of optimization strategies to be used which would otherwise be impossible if list-order application were required.</div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div><br></div><div>If list order is important for you, it is easy enough to define your own &quot;nubBy&quot; function that is not distributive or associative, and can be therefore optimized differently than when you use &quot;Data.List.nubBy&quot;.</div>
<div><br></div><div>This blog post: &lt;<a href="http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html">http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html</a>&gt; is about C, but the principles are the same: it has a fantastic explanation about how &quot;undefined behavior&quot; can be really helpful with simplifying compiler implementation and optimization.</div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div><br></div><div>I hope that makes sense, and if I said anything inaccurate, I am at the mercy of the Haskell-prime mailing list.</div><div><br></div><div>
<br></div><div><div class="gmail_quote">On Thu, Sep 8, 2011 at 9:07 AM, Cale Gibbard <span dir="ltr">&lt;<a href="mailto:cgibbard@gmail.com">cgibbard@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 just tried this in ghci-7.0.3:<br>
<br>
ghci&gt; nubBy (&gt;=) [1,2,3,4]<br>
[1]<br>
<br>
Think about what this is doing: it is excluding 2 from the list<br>
because 2 &gt;= 1, rather than including it because 1 &gt;= 2 fails.<br>
<br>
I think an important convention when it comes to higher order<br>
functions on lists is that to the extent which is possible, the<br>
function parameters take elements from the list (or things computed<br>
from those) in the order in which they occur in the original list.<br>
<br>
If we reimplement it in the obvious way:<br>
ghci&gt; let nubBy f [] = []; nubBy f (x:xs) = x : filter (not . f x) (nubBy f xs)<br>
ghci&gt; nubBy (&gt;=) [1,2,3,4]<br>
[1,2,3,4]<br>
<br>
I&#39;m aware that the Report (strangely!) explicitly leaves the behaviour<br>
of nubBy unspecified for functions which are not equivalence<br>
relations, but the behaviour given by the Report implementation (the<br>
opposite of the current behaviour in GHC) is useful and desirable<br>
nonetheless.<br>
<br>
I&#39;m sure I&#39;ve written about this before. I&#39;m not entirely sure what<br>
happened to the previous thread of discussion about this, but it just<br>
came up again for me, and I decided that I was sufficiently irritated<br>
by it to post again.<br>
<br>
Another thing perhaps worth pointing out is that the parameters to<br>
mapAccumR have always been backwards (compare it with foldr). Few<br>
enough people use this function that I&#39;m fairly sure we could just<br>
change it without harm.<br>
<br>
 - Cale<br>
<br>
_______________________________________________<br>
Haskell-prime mailing list<br>
<a href="mailto:Haskell-prime@haskell.org">Haskell-prime@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-prime" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-prime</a><br>
</blockquote></div><br></div>