haskell - 使用 O(1) 函数编写 CString 的可存储实例以获取总字节长度

Question

我正在尝试写一个storable vector CString 的实例(在我的例子中是空终止的 C 字符)。可存储实例将存储 CString 所在的指针 (Ptr CChar)。因此，向量的长度就是 CString 指针的数量。现在，我编写这个可存储实例的原因是因为它将用于从 FFI CString 进行零复制，然后使用 unsafeCreate 快速构建 ByteString(经过一些转换 - 因此，我们在这里使用快速向量进行中间操作)。为了快速构建 ByteString，可存储实例需要三件事:

• 总长度(以字节为单位)- 可存储实例需要进行簿记分配，以在将每个 CString 添加到向量时存储每个 CString 的长度，以及迄今为止存储的 CString 总长度。假设 C 字符串的总长度不能超过 2^31。因此，Int32/Word32将存储每个CString的长度和总长度。
• 存储 CString 及其长度的函数 - O(n) 时间。此函数将遍历 CString，并存储其长度，并且还将总长度增加 CString 的长度。
• 返回总字节长度的函数 - O(1) 时间。该函数只会从存储总长度的字段中检索值

虽然我知道如何编写自定义可存储实例，但我不知道如何处理这种情况。非常感谢一个简单的代码(可以是一个简单的玩具示例)来展示如何进行自定义簿记，并编写函数来存储/获取簿记结果。

更新 1(澄清)

在我的例子中使用可存储向量实例的原因有两个:使用未装箱类型的快速计算/转换(通过 C FFI 接收的实时数据)，以及快速转换为字节串(以实时发送数据) -通过 IPC 到另一个程序的时间)。对于快速字节串转换，unsafeCreate 非常出色。但是，我们必须知道要分配多少，并且还向其传递一个转换函数。给定一个可存储的向量实例(具有混合类型 - 我将上面的问题简化为 CString 类型)，我很容易构建一个快速转换函数来遍历向量的每个元素并将其转换为字节串。然后，我们只需将其传递给 unsafeCreate 即可。但是，我们还必须向其传递要分配的字节数。 O(n) 递归字节长度计算函数太慢，并且会使构建字节串的开销增加一倍。

Answer 1

听起来你想写这样的东西。请注意，此代码未经测试。

-- The basic type.  Export the type but not the constructors or 
-- accessors from the module.
data StringVector {
   strVecLength :: Word32,               -- Total length
   strVecContents [(Word32, Ptr CChar)]  -- (Length, value) pairs
}

-- Invariants: forall (StringVector len contents), 
--    len == sum (map fst) contents
--    all (\p -> fst p == c_strlen (snd p)) contents


-- The null case.
emptyStrVec :: StringVector
emptyStrVec = StringVector 0 []


-- Put a new Cstring at the head of the vector.  Analogous to ":".
stringVectorCons :: Ptr CChar -> StringVector -> StringVector
stringVectorCons ptr (StringVector len pairs) = 
   StringVector (len + n) $ (n, ptr) : pairs
   where
      n = c_strlen ptr   -- Or whatever the right function name is


-- Extract the head of the vector and the remaining vector.
stringVectorUncons :: StringVector -> ((Word32, Ptr CChar), StringVector)
stringVectorUncons (StringVector len (h:t)) =
   (h, StringVector (len - fst h) t)

之后，您可以根据应用程序添加您可能需要的任何其他功能。只需确保每个函数都保留不变量即可。