Каков наиболее эффективный способ представления конечных (нерекурсивных) значений алгебраического типа?

Каков наиболее эффективный способ сериализации конечных (нерекурсивных) типов алгебраических данных, которые состоят только из конструкторов?

например.

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 представляет их в памяти (это позволяет рекурсию, поэтому, возможно, нужны указатели/ссылки)?

Ответ 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]

Я написал экземпляры таким образом, чтобы показать, что это очень легко и механически и может быть выполнено программой (например, с помощью общего программирования или с шаблоном Haskell). Вы также можете добавить экземпляр для выполнения некоторых задач, если тип Bounded и Enum erable:

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..], чтобы получить вашу кодировку и т.д.

Но, конечно, это было сделано раньше! Я не использую сериализацию много (если когда-либо), но быстрый поиск показывает, что двоичный пакет и двоичный вывод пакет может сделать что-то подобное для вас, без необходимости писать экземпляры самостоятельно. Я посмотрю, сделают ли они то, что вы хотите в первую очередь.

Ответ 2

Что касается представлений haskell в памяти, мы не можем представлять вещи, полностью упакованные обычно, поскольку структуры ленивы, и это означает, что нам нужно косвенное отношение на каждом уровне. Тем не менее, распаковка позволит вам сокрушить эти вещи вместе. Но, насколько я знаю, он не будет упаковывать бит из вложенных конструкторов в одно и то же слово.

Существует оптимизация указателя-метки, которая передает некоторую информацию о конструкторе в указатель, который указывает на него: http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

Подробнее о распаковке см. ниже: http://www.haskell.org/haskellwiki/Performance/Data_types#Unpacking_strict_fields