表示有限(非递归)代数类型值的最有效方法是什么？

Question

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

例如

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如何在内存中表示这些(它允许递归,因此可能需要指针/引用)？

Answer 1

没有完全标准的类可以做到这一点,但是自己制作一个很容易.我将草拟一种方法:

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和Enumerable:

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..]来获取编码等等.

但这肯定已经完成了!我没有多次使用序列化(如果有的话),但快速搜索显示二进制包和二进制派生包 可以为您做类似的事情,而不必自己编写实例.我会看看那些先做你想做的事.

Answer 2

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

有一个指针标记优化,它会在指针中引导一些有关构造函数的信息:http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

有关解压缩的更多信息,请参阅:http://www.haskell.org/haskellwiki/Performance/Data_types#Unpacking_strict_fields