4

我正在尝试为 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。但是，我们还必须传递要分配的字节数。AO(n) 递归字节长度计算函数太慢，并且可以使构建字节串的开销增加一倍。

4

1 回答 1

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)

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

于 2011-12-11T16:08:19.803 回答