Efficienza memoria Haskell - qual è l'approccio migliore?

Puoi espandere la grammatica della matrice in un ADT con la condivisione perfetta con un po 'di inganno:

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

Qui ho generalizzato le tue grammatiche per consentire qualsiasi tipo di dati, non solo Int, e tabulate prenderà la grammatica ed espanderla piegandola su se stessa usando loeb .

loeb è descritto in un articolo di Dan Piponi

L'espansione risultante come un ADT fisicamente non richiede più memoria della grammatica originale - in effetti ci vuole un po 'meno, perché non ha bisogno del fattore di log extra per il dorso della mappa, e non lo fa è necessario memorizzare le stringhe.

A differenza dell'espansione naive, l'utilizzo di loeb mi consente di "legare il nodo" e di condividere i thunk per tutte le occorrenze dello stesso non terminale.

Se vuoi approfondire la teoria di tutto questo, possiamo vedere che RHS potrebbe essere trasformato in un funtore base:

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

e quindi il mio tipo M è solo il punto fisso di quel Functor .

M a ~ Mu (RHS a)

mentre G a consisterebbe in una stringa scelta e una mappa da stringhe a (RHS String a) .

Possiamo quindi espandere G in M cercando la voce in una mappa di stringhe espanse pigramente.

Questa è una sorta di duale di ciò che viene fatto nel pacchetto data-reify , che può assumere un tale funcp base e qualcosa come M e recuperare l'equivalente morale del G da esso. Usano un tipo diverso per i nomi non-terminali, che è fondamentalmente solo un Int .

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

e fornire un combinatore

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

che può essere utilizzato con un'istanza appropriata nei tipi di dati sopra riportati per ottenere un grafico (MatrixGrammar) da una matrice arbitraria. Non eseguirà la deduplicazione dei quadranti identici ma memorizzati separatamente, ma recupererà tutta la condivisione presente nel grafico originale.

In Haskell, il tipo String è un alias per [Char], che è un normale list di Char di Haskell, non un vettore o una matrice. Char è un tipo che contiene un singolo carattere Unicode. I valori letterali stringa sono, a meno che non si utilizzi un'estensione di linguaggio, valori di tipo String.

Penso che si possa dedurre da quanto sopra che String non è una rappresentazione molto compatta o comunque efficiente. Le rappresentazioni alternative comuni per le stringhe includono i tipi forniti da Data.Text e Data.ByteString.

Per maggiore praticità, è possibile utilizzare -XOverloadedStrings in modo che sia possibile utilizzare valori letterali stringa come rappresentazioni di un tipo di stringa alternativo, come fornito da Data.ByteString.Char8. Questo è probabilmente il modo più efficiente in termini di spazio per utilizzare convenientemente le stringhe come identificatori.

Per quanto riguarda Int, è un tipo a larghezza fissa, ma non vi è alcuna garanzia su quanto sia ampio tranne che deve essere sufficientemente ampio per contenere i valori [-2 ^ 29 .. 2 ^ 29-1] . Ciò suggerisce che siano almeno 32 bit, ma non esclude che siano 64 bit. Data.Int ha alcuni tipi più specifici, Int8-Int64, che puoi usare se hai bisogno di una larghezza specifica.

Modifica per aggiungere informazioni

Non credo che la semantica di Haskell specifichi alcunché sulla condivisione dei dati in entrambi i modi. Non dovresti aspettarti che due letterali String, o due di qualsiasi dato costruito, facciano riferimento allo stesso oggetto "canonico" in memoria. Se dovessi legare un valore costruito ad un nuovo nome (con let, un pattern match, ecc.) Entrambi i nomi molto probabilmente si riferiscono agli stessi dati, ma se lo fanno o no non sono realmente visibili a causa della natura immutabile di Dati Haskell.

Per motivi di efficienza dello storage, è possibile intern le stringhe, che essenzialmente memorizza una rappresentazione canonica di ciascuna in una tabella di ricerca di qualche tipo, in genere una tabella hash. Quando si intern un oggetto, si ottiene un descrittore per esso indietro, e è possibile confrontare questi descrittori con gli altri per vedere se sono lo stesso molto più a buon mercato di quanto si potrebbe stringhe, e sono anche spesso molto più piccoli.

Per una biblioteca che esegue interning, puoi utilizzare link

Come per decidere quale dimensione intera usare in fase di esecuzione, è abbastanza facile scrivere codice che dipende dalle classi di tipo Integral o Num invece dei tipi numerici concreti. L'inferenza del tipo ti darà i tipi più generali che può automaticamente. Potresti quindi avere alcune funzioni diverse con tipi esplicitamente ristretti a specifici tipi numerici che potresti scegliere a runtime per eseguire l'installazione iniziale, e successivamente tutte le altre funzioni polimorfiche funzionerebbero allo stesso modo su ognuna di esse. Per esempio:.

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

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Modifica : ulteriori informazioni sull'internamento

Se si desidera solo stringhe interne, è possibile creare un nuovo tipo che racchiuda una stringa (preferibilmente un testo o una stringa di byte) e un intero piccolo insieme.

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

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

Quello che fa 'intern' è cercare la stringa in una HashMap di riferimento debole dove i testi sono chiavi e InternedStrings sono valori. Se viene trovata una corrispondenza, "stag" restituisce il valore. In caso contrario, crea un nuovo valore di InternedString con il testo originale e un id intero univoco (motivo per cui ho incluso il vincolo MonadIO: potrebbe utilizzare una monade di stato o un'operazione non sicura per ottenere l'id univoco, ci sono molte possibilità) e lo memorizza sulla mappa prima di restituirlo.

Ora ottieni un confronto veloce basato sull'ID intero e solo una copia di ogni stringa univoca.

La biblioteca interna di Edward Kmett applica lo stesso principio, più o meno, in un modo molto più generale, in modo che i termini dei dati strutturati interi siano sottoposti a hashing, memorizzati in modo univoco e dati un'operazione di confronto veloce. È un po 'scoraggiante e non particolarmente documentato, ma potrebbe essere disposto ad aiutare se lo chiedi; oppure potresti provare prima l'implementazione interna della stringa per verificare se è sufficiente.