Eficiencia de la memoria Haskell: ¿cuál es el mejor enfoque?

Estamos implementando una biblioteca de compresión matricial basada en una sintaxis gramatical bidimensional modificada. Ahora tenemos dos enfoques para nuestros tipos de datos: ¿cuál será mejor en caso de uso de memoria? (Queremos comprimir algo;)).

Las gramáticas contienen No Terminales con exactamente 4 Producciones o una Terminal en el lado derecho. Necesitaremos los nombres de Producciones para verificaciones de igualdad y minimización gramatical.

El primero:

-- | Type synonym for non-terminal symbols
type NonTerminal = String

-- | Data type for the right hand side of a production
data RightHandSide = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal Int

-- | Data type for a set of productions
type ProductionMap = Map NonTerminal RightHandSide

data MatrixGrammar = MatrixGrammar {
    -- the start symbol
    startSymbol :: NonTerminal,
    -- productions
    productions :: ProductionMap    
    } 

Aquí, nuestros datos RightHandSide guardan solo los nombres de cadenas para determinar las próximas producciones, y lo que no sabemos aquí es cómo Haskell guarda estas cadenas. Por ejemplo, la matriz [[0, 0], [0, 0]] tiene 2 producciones:

a = Terminal 0
aString = "A"
b = DownStep aString aString aString aString
bString = "B"
productions = Map.FromList [(aString, a), (bString, b)]

Entonces, la pregunta aquí es ¿con qué frecuencia se guarda realmente la cadena "A"? ¿Una vez en aString, 4 veces en by una vez en producciones o solo una vez en aString y los otros solo tienen referencias "más baratas"?

El segundo:

data Production = NonTerminal String Production Production Production Production
                | Terminal String Int 

type ProductionMap = Map String Production

aquí el término "Terminal" es un poco engañoso porque en realidad es la producción la que tiene un terminal en el lado derecho. La misma matriz:

a = Terminal "A" 0
b = NonTerminal "B" a a a a
productions = Map.fromList [("A", a), ("B", b)]

y la pregunta similar: ¿con qué frecuencia Haskell guarda internamente la producción? Posiblemente eliminaremos los nombres dentro de las producciones si no los necesitamos, pero no estamos seguros de esto en este momento.

Digamos que tenemos una gramática con alrededor de 1000 producciones. ¿Qué enfoque consumirá menos memoria?

Finalmente una pregunta sobre enteros en Haskell: actualmente estamos planeando tener un nombre como Strings. Pero podríamos cambiar fácilmente a nombres enteros porque con 1000 producciones tendremos nombres con más de 4 caracteres (que supongo que es de 32 bits). ¿Cómo maneja Haskell esto? ¿Es un Int siempre de 32 bits e Integer asigna memoria que realmente necesita?

También leí esto: Diseño de prueba de la semántica de valor / referencia de Haskell, pero no puedo entender qué significa eso exactamente para nosotros. Soy más un niño imperativo de Java que un buen programador funcional: P

Puede expandir su gramática matricial en un ADT con un intercambio perfecto con un poco de truco:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import Data.Map
import Data.Foldable
import Data.Functor
import Data.Traversable

-- | Type synonym for non-terminal symbols
type NonTerminal = String

-- | Data type for the right hand side of a production
data RHS a = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal a
  deriving (Eq,Ord,Show,Read,Functor, Foldable, Traversable)

data G a = G NonTerminal (Map NonTerminal (RHS a))
  deriving (Eq,Ord,Show,Read,Functor)

data M a = Q (M a) (M a) (M a) (M a) | T a
  deriving (Functor, Foldable, Traversable)

tabulate :: G a -> M a
tabulate (G s pm) = loeb (expand <$> pm) ! s where
  expand (DownStep a11 a12 a21 a22) m = Q (m!a11) (m!a12) (m!a21) (m!a22)
  expand (Terminal a)               _ = T a

loeb :: Functor f => f (f b -> b) -> f b
loeb x = xs where xs = fmap ($xs) x

Aquí generalicé sus gramáticas para permitir cualquier tipo de datos, no solo Int, y tabulatetomaré la gramática y la expandiré doblándola sobre sí misma usando loeb.

loebse describe en un artículo de Dan Piponi

La expansión resultante como ADT no requiere físicamente más memoria que la gramática original; de hecho, toma bastante menos, porque no necesita el factor de registro adicional para la columna vertebral del Mapa, y no necesita almacenar las cuerdas en absoluto.

A diferencia de la expansión ingenua, el uso loebme permite 'atar el nudo' y compartir los thunks para todas las ocurrencias del mismo no terminal.

Si desea profundizar más en la teoría de todo esto, podemos ver que RHSpodría convertirse en un functor base:

data RHS t nt = Q nt nt nt nt | L t

y luego mi tipo M es solo el punto fijo de eso Functor.

M a ~ Mu (RHS a)

while G aconsistiría en una cadena elegida y un mapa de cadenas a (RHS String a).

Luego podemos expandirnos Gal Mbuscar la entrada en un mapa de cadenas expandidas perezosamente.

Este es el doble de lo que se hace en el data-reifypaquete, que puede tomar un functor tan básico, y algo así Mcomo recuperar el equivalente moral de usted G. Usan un tipo diferente para los nombres no terminales, que básicamente es solo un Int.

data Graph e = Graph [(Unique, e Unique)] Unique

y proporcionar un combinador

reifyGraph :: MuRef s => s -> IO (Graph (DeRef s))

que se puede usar con una instancia apropiada en los tipos de datos anteriores para obtener un gráfico (MatrixGrammar) de una matriz arbitraria. No hará deduplicación de cuadrantes idénticos pero almacenados por separado, pero recuperará todo el intercambio que está presente en el gráfico original.

En Haskell, el tipo de cadena es un alias para [Char], que es una lista normal de Haskell de Char, no un vector o matriz. Char es un tipo que tiene un solo carácter Unicode. Los literales de cadena son, a menos que use una extensión de idioma, valores de tipo de cadena.

Creo que puedes deducir de lo anterior que String no es una representación muy compacta o eficiente. Las representaciones alternativas comunes para cadenas incluyen los tipos proporcionados por Data.Text y Data.ByteString.

Para mayor comodidad, puede usar -XOverloadedStrings para que pueda usar literales de cadena como representaciones de un tipo de cadena alternativo, como el proporcionado por Data.ByteString.Char8. Esa es probablemente la forma más eficiente en el espacio para usar convenientemente cadenas como identificadores.

En lo que respecta a Int, es un tipo de ancho fijo, pero no hay garantía sobre qué tan ancho es, excepto que debe ser lo suficientemente ancho como para contener los valores [-2 ^ 29 .. 2 ^ 29-1]. Esto sugiere que son al menos 32 bits, pero no descarta que sean 64 bits. Datos: tiene algunos tipos más específicos, Int8-Int64, que puede usar si necesita un ancho específico.

Editar para agregar información

No creo que la semántica de Haskell especifique nada sobre el intercambio de datos de ninguna manera. No debe esperar que dos literales de cadena, o dos de los datos construidos, se refieran al mismo objeto 'canónico' en la memoria. Si vinculara un valor construido a un nuevo nombre (con let, una coincidencia de patrón, etc.), ambos nombres probablemente se referirían a los mismos datos, pero si lo hacen o no no es realmente visible debido a la naturaleza inmutable de Datos de Haskell.

En aras de la eficiencia del almacenamiento, podría internar las cadenas, que esencialmente almacenan una representación canónica de cada una en una tabla de búsqueda de algún tipo, generalmente una tabla hash. Cuando internas un objeto, obtienes un descriptor para él, y puedes comparar esos descriptores con otros para ver si son los mismos mucho más baratos que las cadenas, y a menudo también son mucho más pequeños.

Para una biblioteca que realiza internados, puede usar https://github.com/ekmett/intern/

En cuanto a decidir qué tamaño de entero usar en tiempo de ejecución, es bastante fácil escribir código que depende de clases de tipo Integral o Num en lugar de tipos numéricos concretos. La inferencia de tipos le dará los tipos más generales que puede automáticamente. Luego, podría tener algunas funciones diferentes con tipos estrechamente explícitos a tipos numéricos específicos de los que podría elegir uno en tiempo de ejecución para realizar la configuración inicial, y luego todas las demás funciones polimórficas funcionarían igual en cualquiera de ellos. P.ej:

polyConstructor :: Integral a => a -> MyType a
int16Constructor :: Int16 -> MyType Int16
int32Constructor :: Int32 -> MyType Int32

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Editar : más información sobre pasantías

Si solo desea internar cadenas, puede crear un nuevo tipo que envuelva una cadena (preferiblemente un Texto o ByteString) y un pequeño entero juntos.

data InternedString = { id :: Int32, str :: Text }
instance Eq InternedString where
    {x, _ } == {y, _ }  =  x == y

intern :: MonadIO m => Text -> m InternedString

Lo que hace 'intern' es buscar la cadena en un HashMap de referencia débil donde los Textos son claves e InternedStrings son valores. Si se encuentra una coincidencia, 'interno' devuelve el valor. De lo contrario, crea un nuevo valor InternedString con el texto original y una identificación entera única (por eso incluí la restricción MonadIO; podría usar una mónada State o alguna operación insegura para obtener la identificación única; hay muchas posibilidades) y lo almacena en el mapa antes de devolverlo.

Ahora obtiene una comparación rápida basada en la identificación entera y solo tiene una copia de cada cadena única.

La biblioteca interna de Edward Kmett aplica el mismo principio, más o menos, de una manera mucho más general, de modo que los términos de datos estructurados completos se codifican, se almacenan de forma única y se les da una operación de comparación rápida. Es un poco desalentador y no está particularmente documentado, pero podría estar dispuesto a ayudar si lo solicita; o simplemente puede probar su propia implementación de internados de cadenas primero para ver si ayuda lo suficiente.