haskell - 如何在 Haskell 中将树数据结构保存为二进制文件

Question

我正在尝试使用 Haskell 将一个简单(但相当大)的树结构保存到一个二进制文件中。结构看起来像这样:-- 为简单起见，假设每个节点只有 4 个 child
数据树 = 节点 [树] |叶 [Int]

这是我需要在磁盘上查看数据的方式:

每个节点以四个 32 位偏移量开始，然后跟随子节点。

我不太关心叶子，假设它只是 n 个连续的 32 位数字。

出于实践目的，我需要一些节点标签或其他一些附加数据
但现在我也不在乎那么多。

在我看来，Haskellers 在编写二进制文件时的首选是 Data.Binary.Put 库。但是，我在子弹#1 中遇到了问题。特别是，当我将一个节点写入文件时，要写下子偏移量，我需要知道我当前的偏移量和每个子节点的大小。

这不是 Data.Binary.Put 提供的东西，所以我认为这一定是 Monad 转换器的完美应用。但即使它听起来很酷且实用，但到目前为止我还没有成功地使用这种方法。

我问了另外两个我认为可以帮助我解决问题的问题 here和 here .我必须说，每次我收到非常好的答案，帮助我进一步进步，但不幸的是，我仍然无法从整体上解决问题。

Here是我到目前为止所得到的，它仍然泄漏了太多的内存而不实用。

我很想拥有使用这种功能方法的解决方案，但也会感谢任何其他解决方案。

Answer 1

我会考虑两种基本方法。如果整个序列化结构很容易放入内存，您可以将每个节点序列化为一个惰性字节串，并仅使用每个节点的长度来计算与当前位置的偏移量。

serializeTree (Leaf nums)  = runPut (mapM_ putInt32 nums)
serializeTree (Node subtrees) = mconcat $ header : childBs
 where
  childBs = map serializeTree subtrees
  offsets = scanl (\acc bs -> acc+L.length bs) (fromIntegral $ 2*length subtrees) childBs
  header = runPut (mapM_ putInt32 $ init offsets)

另一种选择是，在序列化节点后，返回并使用适当的数据重新写入偏移字段。如果树很大，这可能是唯一的选择，但我不知道支持这个的序列化库。这将涉及在 IO 工作和 seek到正确的位置。