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

これを行う完全に標準的なクラスはありませんが、自分で作成するのは非常に簡単です。これを行う 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) で実行できることを示すためです。タイプがerableBoundedである場合は、インスタンスを追加していくつかのレッグワークを実行することもできます。Enum

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

に追加deriving (Bounded, Show)するとR、書き込むインスタンスが 1 つ少なくなります。

とにかく、これで評価allValues :: [P]して戻す[A,B C,B (D F),B (D G),B E]ことができます。これを使用zipし[0..]て、エンコーディングなどを取得できます。

しかし、確かにこれは以前に行われました！私はシリアライゼーションをあまり (もしあったとしても) 使用していませんが、簡単に検索すると、binary パッケージとbinary-derive パッケージ が、インスタンスを自分で作成しなくても同様のことができることがわかります。それらが最初にあなたが望むことをするかどうかを確認します。

于 2013-03-22T17:10:21.613 に答える