What is the best way to represent a short bit string?

Question

I want to imagine a string up to 120 bits long, and the speed is critical. I need to be able to build a bit tool using repeating snoc operations, and then use it with repeating uncons operations. One idea is to steal a Word128 implementation from data-dword and use something like this to build:

 empty = 1 snoc xs x = (xs `shiftL` 1) .|. x 

But the villain seems a little ugly, having countLeadingZeros first and a left shift to eliminate them before he can read the elements by moving and masking the high bits.

Is there an even nicer way, at least such a quick or faster way, which is not too unpleasant?

---

Context

Phil Ruffwind proposed a lens at version for Data.Map , but all implementations are still significantly slower than the naive lens implementation currently used when key comparison is cheap. If I could create a very cheap representation of the write path when searching, and then use it with a specialized version of insert or delete very efficiently, then maybe I could make it worth it.

Answer 1

I am not sure if this is appropriate. I am afraid that I am reprogramming countLeadingZeros in some form ...

Anyway, the idea is that the snoc bit on the left is shifted to the right. Then we can “count” the trailing zeros of x using x-1 and XOR. The result of "counting" is the mask "00..01..11", which, roughly speaking, is a unary representation of trailing zeros. We do not convert this unary to binary, because we do not need: with some work at the bit level, we can uncons.

What follows is an unverified and unproven code.

 import Data.Word import Data.Bits import Text.Printf type T = Word64 -- can be adapted to any WordN -- for pretty printing pr :: T -> String pr x = printf "%064b\n" x empty :: T empty = shiftL 1 63 snoc :: T -> T -> T snoc x xs = shiftR xs 1 .|. (shiftL x 63) -- returns (head, tail) -- head is not normalized (0 or 1), only (0 or /=0) uncons :: T -> (T, T) uncons xs = let -- example -- 0101001100000000000 xs y = (xs `xor` (xs - 1)) -- 0000000111111111111 y z = shiftR y 1 + 1 -- 0000000100000000000 z z' = shiftL z 1 -- 0000001000000000000 z' in (xs .&. z' , (xs .&. complement z) .|. z' )