表示短位串的最佳方法是什么？

Question

我想表示一个高达120位的字符串,速度至关重要.我需要能够通过重复snoc操作构建一个位串,然后通过重复操作来消耗它uncons.一个想法是窃取Word128from 的实现data-dword并使用这样的东西来构建:

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

但是,在countLeadingZeros通过移位和屏蔽高位来读取元素之前,不必要的东西似乎变得有点难看,不得不首先向左移动以消除它们.

是否有一些更愉快的方式,至少同样快,或更快的方式,不是太不愉快？

---

上下文

Phil Ruffwind提出了一个版本的lens's atfor Data.Map,但到目前为止所有的实现都比lens当前密钥比较便宜时使用的天真实现要慢得多.如果我可以在查找条目时生成一个非常便宜的条目路径表示,然后使用专门版本的insert或者非常有效地使用它delete,那么也许我可以使这个值得.

Answer 1

我不确定这是否符合条件。countLeadingZeros我担心我正在以某种形式重新实施......

不管怎样，这个想法是从左边嗅探比特，然后向右移动。x然后，我们可以使用x-1XOR 来“计算”尾随零。“计数”的结果是掩码“00..01..11”，粗略地说，它是尾随零的一元表示。我们不会将此一元转换为二进制，因为我们不需要：通过一些位级工作，我们可以取消。

以下是未经测试和验证的代码。

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' )