11

序列化仅由构造函数组成的有限（非递归）代数数据类型的最有效方法是什么？

例如

p = A
  | B q

q = C 
  | D r
  | E

r = F
  | G

手动枚举这个微不足道的定义的所有有效组合是可能的：

A      0x00
B C    0x01
B D F  0x02
B D G  0x03
B E    0x04

  • 这里有更广泛的理论吗？

  • 如果我们然后添加非构造函数类型，例如 int 等，怎么样？

  • Haskell 如何在内存中表示这些（它允许递归，因此可能需要指针/引用）？

4

2 回答 2

7

没有完全标准的类可以做到这一点，但自己制作一个非常容易。我将勾勒出一种方法：

data P = A | B Q deriving Show
data Q = C | D R | E deriving Show
data R = F | G  deriving Show

class Finite a where
    allValues :: [a]

instance Finite P where
    allValues = [A] ++ map B allValues

instance Finite Q where
    allValues = [C] ++ map D allValues ++ [E]

instance Finite R where
    allValues = [F] ++ [G]

我以这种方式编写了实例，以表明它非常简单和机械，并且可以通过程序来完成（例如，使用通用编程或 Template Haskell）。Bounded如果类型是可擦除的，您还可以添加一个实例来为您做一些工作Enum：

instance (Bounded a, Enum a) => Finite a where
    allValues = [minBound..maxBound]

如果您现在添加deriving (Bounded, Show)到R，那就少写一个实例！

无论如何，现在我们可以评估allValues :: [P]并返回[A,B C,B (D F),B (D G),B E]- 然后您可以zip使用它[0..]来获取您的编码等等。

但肯定以前有人做过！我没有过多地使用序列化（如果有的话），但是快速搜索表明二进制包和二进制派生包 可以为您做类似的事情，而无需自己编写实例。我会先看看那些做你想做的事。

于 2013-03-22T17:10:21.613 回答
6

至于内存中的 haskell 表示，我们通常不能表示完全打包的东西，因为结构是惰性的，这意味着我们需要在每个级别上进行间接处理。也就是说，拆包会让你把这些东西压在一起。但是，据我所知，它不会将嵌套构造函数中的位打包到同一个单词中。

有一个指针标记优化，它在指向它的指针中推送有关构造函数的一些信息：http: //hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

有关拆包的更多信息，请参见：http ://www.haskell.org/haskellwiki/Performance/Data_types#Unpacking_strict_fields

于 2013-03-22T17:21:19.113 回答