On Sat, Oct 15, 2011 at 11:00 AM, Bas van Dijk <span dir="ltr">&lt;<a href="mailto:v.dijk.bas@gmail.com">v.dijk.bas@gmail.com</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div><div></div><div class="h5">Another problem is that the default implementation of popCount uses a &#39;-&#39;:</div></div>
<br>
    popCount          :: a -&gt; Int<br>
    popCount = go 0<br>
      where<br>
        go !c 0 = c<br>
        go c w = go (c+1) (w .&amp;. w - 1)</blockquote><div><br></div><div>I wonder what kind of bitwise algorithms will be hard to implement without using arithmetic. For example, the -1 trick is very common in bit twiddling:</div>

<div><br></div><div><a href="http://graphics.stanford.edu/~seander/bithacks.html">http://graphics.stanford.edu/~seander/bithacks.html</a></div><div><br></div><div>I guess they can be implemented outside the type class, with an extra num constraint, but then we can&#39;t use specialized instructions where available, as in the case of popCount. Or perhaps we can if we use rules to rewrite e.g. popCount :: Word32 -&gt; Int to popCount32# (which turns into a single assembly instruction).</div>

<div><br></div><div>-- Johan</div><div> </div></div>