Eficiência de memória Haskell - qual é a melhor abordagem?

Estamos implementando uma biblioteca de compactação de matriz baseada em uma sintaxe gramatical bidimensional modificada. Agora, temos duas abordagens para nossos tipos de dados - qual será melhor em caso de uso de memória? (queremos compactar algo;)).

As gramáticas contêm NonTerminals com exatamente 4 Productions ou um Terminal no lado direito. Vamos precisar dos nomes de Productions para verificação de igualdade e minimização gramatical.

O primeiro:

-- | 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    
    } 

Aqui, nossos dados RightHandSide salvam apenas nomes de String para determinar as próximas produções, e o que não sabemos aqui é como Haskell salva essas strings. Por exemplo, a matriz [[0, 0], [0, 0]] possui 2 produções:

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

Portanto, a questão aqui é com que frequência a string "A" é realmente salva? Uma vez em aString, 4 vezes em be uma vez em produções ou apenas uma vez em aString e os outros apenas têm referências "mais baratas"?

O segundo:

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

type ProductionMap = Map String Production

aqui o termo "Terminal" é um pouco enganador, porque na verdade é a produção que tem um terminal no lado direito. A mesma matriz:

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

e a pergunta semelhante: com que frequência a produção é salva internamente por Haskell? Possivelmente colocaremos os nomes dentro das produções se não precisarmos deles, mas não temos certeza no momento.

Digamos que tenhamos uma gramática com cerca de 1000 produções. Qual abordagem consumirá menos memória?

Finalmente, uma pergunta sobre números inteiros em Haskell: Atualmente, estamos planejando ter o nome como Strings. Mas poderíamos facilmente mudar para nomes inteiros porque, com 1000 produções, teremos nomes com mais de 4 caracteres (o que, suponho, é 32 bits?). Como Haskell lida com isso. Um Int sempre é de 32 bits e um número inteiro aloca a memória de que realmente precisa?

Também li o seguinte: Teste da semântica de valor / referência de Haskell - mas não consigo descobrir o que isso significa exatamente para nós - sou mais uma criança java imperativa do que um bom programador funcional: P

Você pode expandir sua gramática matricial em um ADT com compartilhamento perfeito com um pouco de truque:

{-# 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

Aqui eu generalizei suas gramáticas para permitir qualquer tipo de dados, não apenas Int, e tabulatepegarei a gramática e a expandirei, dobrando-a sobre si mesma usando loeb.

loebé descrito em um artigo de Dan Piponi

A expansão resultante como um ADT fisicamente não ocupa mais memória do que a gramática original - na verdade, leva um pouco menos, porque não precisa do fator de log extra para a coluna Map e não precisa armazenar as cordas de todo.

Ao contrário da expansão ingênua, usar loebpermite-me 'dar o nó' e compartilhar os thunks para todas as ocorrências do mesmo não terminal.

Se você quiser se aprofundar mais na teoria de tudo isso, podemos ver que isso RHSpode se transformar em um functor básico:

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

e então meu tipo M é apenas o ponto fixo disso Functor.

M a ~ Mu (RHS a)

while G aconsistiria em uma string escolhida e um mapa de strings para (RHS String a).

Podemos, então, expandir Gem Mpelo lookup-se a entrada em um mapa de cordas expandidas preguiçosamente.

Esse é o tipo de dualidade do que é feito no data-reifypacote, que pode levar esse função de base, e algo como Me recuperar o equivalente moral do seu G. Eles usam um tipo diferente para os nomes não terminais, que é basicamente apenas um Int.

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

e fornecer um combinador

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

que pode ser usado com uma instância apropriada nos tipos de dados acima para obter um gráfico (MatrixGrammar) de uma matriz arbitrária. Não fará a desduplicação de quadrantes idênticos, mas armazenados separadamente, mas recuperará todo o compartilhamento presente no gráfico original.

No Haskell, o tipo String é um alias para [Char], que é uma lista Haskell regular de Char, não um vetor ou matriz. Char é um tipo que contém um único caractere Unicode. Literais de string são, a menos que você use uma extensão de idioma, valores do tipo String.

Eu acho que você pode adivinhar, acima, que String não é uma representação muito compacta ou eficiente. Representações alternativas comuns para seqüências de caracteres incluem os tipos fornecidos por Data.Text e Data.ByteString.

Para maior comodidade, você pode usar -XOverloadedStrings para poder usar literais de sequência como representações de um tipo de sequência alternativo, como o fornecido por Data.ByteString.Char8. Essa é provavelmente a maneira mais eficiente em termos de espaço para usar convenientemente seqüências de caracteres como identificadores.

No que diz respeito a Int, é um tipo de largura fixa, mas não há garantia de quão larga é, exceto que ela deve ser larga o suficiente para manter os valores [-2 ^ 29 .. 2 ^ 29-1]. Isso sugere pelo menos 32 bits, mas não descarta ser de 64 bits. O Data.Int possui alguns tipos mais específicos, Int8-Int64, que você pode usar se precisar de uma largura específica.

Editar para adicionar informações

Não acredito que a semântica de Haskell especifique algo sobre o compartilhamento de dados de qualquer maneira. Você não deve esperar que dois literais String ou dois dados construídos se refiram ao mesmo objeto 'canônico' na memória. Se você vincular um valor construído a um novo nome (com let, uma correspondência de padrão etc.), os dois nomes provavelmente se referirão aos mesmos dados, mas se eles fazem ou não não são realmente visíveis devido à natureza imutável de Dados Haskell.

Por uma questão de eficiência de armazenamento, você pode internar as seqüências, que essencialmente armazenam uma representação canônica de cada uma em uma tabela de pesquisa de algum tipo, geralmente uma tabela de hash. Ao internar um objeto, você recebe um descritor para ele de volta e pode comparar esses descritores com outros para ver se eles são os mesmos com muito mais baixo custo do que você poderia com as seqüências de caracteres, e geralmente também são muito menores.

Para uma biblioteca que realiza internação, você pode usar https://github.com/ekmett/intern/

Quanto à decisão de qual tamanho inteiro usar no tempo de execução, é bastante fácil escrever código que depende das classes de tipo Integral ou Num, em vez de tipos numéricos concretos. A inferência de tipo fornecerá os tipos mais gerais possíveis automaticamente. Você poderia então ter algumas funções diferentes com tipos explicitamente restritos a tipos numéricos específicos, dos quais você poderia escolher um em tempo de execução para fazer a configuração inicial e, posteriormente, todas as outras funções polimórficas funcionariam da mesma maneira em qualquer uma delas. Por exemplo:

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

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Edit : Mais informações sobre interning

Se você deseja apenas estender seqüências de caracteres, você pode criar um novo tipo que agrupe uma sequência (de preferência um Texto ou ByteString) e um pequeno número inteiro.

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

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

O que 'intern' faz é procurar a string em um HashMap de referência fraca, onde Textos são chaves e InternedStrings são valores. Se uma correspondência for encontrada, 'intern' retornará o valor. Caso contrário, ele cria um novo valor InternedString com o texto original e um ID inteiro único (e foi por isso que incluí a restrição MonadIO; ele poderia usar uma mônada estadual ou alguma operação insegura para obter o ID exclusivo; há muitas possibilidades) e armazena-o no mapa antes de devolvê-lo.

Agora você obtém uma comparação rápida com base no número inteiro e possui apenas uma cópia de cada sequência exclusiva.

A biblioteca interna de Edward Kmett aplica o mesmo princípio, mais ou menos, de uma maneira muito mais geral, para que termos de dados estruturados inteiros sejam divididos em hash, armazenados de forma exclusiva e com uma operação de comparação rápida. É um pouco assustador e não está particularmente documentado, mas ele pode estar disposto a ajudar, se você perguntar; ou você pode apenas tentar sua própria implementação de cadeia de caracteres para verificar se isso ajuda o suficiente.