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

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，您还可以添加一个实例来为您做一些工作。和 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..]获取您的编码等。

但肯定以前有人做过!我没有过多使用序列化(如果有的话)，但快速搜索显示 the binary package和 the binary-derive package可以为您做类似的事情，而无需自己编写实例。我会先看看那些做你想做的事。