haskell - ¿Cuál es la forma más eficiente de representar valores de tipo algebraico finitos(no recursivos)?

serialization algebraic-data-types

Question

¿Cuál es la forma más eficiente de serializar tipos de datos algebraicos finitos (no recursivos) que están compuestos solo por constructores?

p.ej

p = A
  | B q

q = C 
  | D r
  | E

r = F
  | G

Es posible enumerar manualmente todas las combinaciones válidas para esta definición trivialmente pequeña:

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

• ¿Hay alguna teoría más amplia aquí?

• ¿Qué tal si luego agregamos tipos que no son de constructor, como ints, etc.?

• ¿Cómo representa Haskell estos en la memoria (permite la recursión, por lo que probablemente serán necesarios los punteros / referencias)?

Answer 1

En cuanto a las representaciones haskell en memoria, no podemos representar las cosas completamente empaquetadas, ya que las estructuras son flojas, y eso significa que necesitamos un direccionamiento indirecto en cada nivel. Dicho esto, desempaquetar te permitirá aplastar estas cosas juntas. Pero, hasta donde yo sé, no empacará bits de constructores anidados en la misma palabra.

Hay una optimización de etiquetado de puntero que arroja cierta información sobre el constructor en el puntero que lo dirige: http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

Para obtener más información sobre cómo desempacar, consulte esto: http://www.haskell.org/haskellwiki/Performance/Data_types#Unpacking_strict_fields

Answer 2

No hay una clase completamente estándar que haga esto, pero es bastante fácil hacer uno tú mismo. Voy a esbozar una forma de hacer esto:

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]

He escrito las instancias de esta manera para mostrar que es muy fácil y mecánico y que podría hacerse con un programa (por ejemplo, con programación genérica o con Template Haskell). También puede agregar una instancia para hacer algo de trabajo por usted, siempre que el tipo sea Bounded y Enumerable:

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

Si ahora agrega deriving (Bounded, Show) a R , ¡esa es una instancia menos para escribir!

De todos modos, ahora podemos evaluar todos los allValues :: [P] y obtener [A,BC,B (DF),B (DG),BE] - que luego puede zip con [0..] para obtener su codificación y así en.

¡Pero seguramente esto ya se hizo antes! No uso mucho la serialización (si es que lo hago alguna vez), pero una búsqueda rápida muestra que el paquete binario y el paquete binary-derive pueden hacer algo similar para usted, sin tener que escribir las instancias usted mismo. Vería si hacen lo que quieren primero.