haskell - 表示短位串的最佳方式是什么？

Question

我想表示最多约 120 位的字符串，速度至关重要。我需要能够通过重复 snoc 来构建位串操作，然后重复使用 uncons操作。一种想法是窃取 Word128 的实现。来自 data-dword并使用这样的东西来构建:

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

但是 unconsing 似乎有点难看，必须先 countLeadingZeros并左移以消除它们，然后才能通过移位和屏蔽高位来读取元素。
是否有一些更愉快的方式至少一样快，或者一些更快的方式不太令人不快？

语境
Phil Ruffwind 提出了 lens 的版本。的 at对于 Data.Map , 但到目前为止所有的实现都比简单的实现慢得多 lens当前在 key 比较便宜时使用。如果我可以在查找条目时生成一个非常便宜的路径表示，然后使用 insert 的专用版本非常有效地使用它或 delete ，那么也许我可以让这变得有值(value)。

Answer 1

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

无论如何，这个想法是从左边开始，向右移动。然后，我们可以“计算”x 的尾随零。使用 x-1和一个异或。 “计数”的结果是一个掩码“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' )