Proposal: Remove Num superclass of Bits

Johan Tibell johan.tibell at gmail.com
Sat Oct 15 20:10:41 CEST 2011


On Sat, Oct 15, 2011 at 11:00 AM, Bas van Dijk <v.dijk.bas at gmail.com> wrote:

> Another problem is that the default implementation of popCount uses a '-':
>
>    popCount          :: a -> Int
>    popCount = go 0
>      where
>        go !c 0 = c
>        go c w = go (c+1) (w .&. w - 1)


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:

http://graphics.stanford.edu/~seander/bithacks.html

I guess they can be implemented outside the type class, with an extra num
constraint, but then we can'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 -> Int to popCount32# (which turns into a single
assembly instruction).

-- Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20111015/077e746a/attachment.htm>


More information about the Libraries mailing list