Wdrażamy bibliotekę kompresji macierzy opartą na zmodyfikowanej dwuwymiarowej składni gramatycznej. Teraz mamy dwa podejścia do naszych typów danych - które będzie lepsze w przypadku użycia pamięci? (chcemy coś skompresować;)).
Gramatyki zawierają NonTerminals z dokładnie 4 produkcjami lub Terminal po prawej stronie. Będziemy potrzebować nazw Productions do kontroli równości i minimalizacji gramatyki.
Pierwszy:
-- | 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
}
Tutaj nasze dane RightHandSide zapisują tylko nazwy ciągów, aby określić następne produkcje, a nie wiemy tutaj, w jaki sposób Haskell zapisuje te ciągi. Na przykład macierz [[0, 0], [0, 0]] ma 2 produkcje:
a = Terminal 0
aString = "A"
b = DownStep aString aString aString aString
bString = "B"
productions = Map.FromList [(aString, a), (bString, b)]
Pytanie brzmi więc, jak często naprawdę zapisywany jest ciąg „A”? Raz w aString, 4 razy wb i raz w produkcjach, czy tylko raz w aString, a inni mają tylko „tańsze” referencje?
Drugi:
data Production = NonTerminal String Production Production Production Production
| Terminal String Int
type ProductionMap = Map String Production
tutaj termin „Terminal” jest nieco mylący, ponieważ w rzeczywistości jest to produkcja, która ma terminal po prawej stronie. Ta sama matryca:
a = Terminal "A" 0
b = NonTerminal "B" a a a a
productions = Map.fromList [("A", a), ("B", b)]
i podobne pytanie: jak często Haskell oszczędza produkcję wewnętrznie? Być może upuścimy nazwiska w produkcjach, jeśli nie będziemy ich potrzebować, ale nie jesteśmy w tej chwili pewni.
Powiedzmy, że mamy gramatykę z około 1000 produkcji. Które podejście zużyje mniej pamięci?
Na koniec pytanie o liczby całkowite w Haskell: Obecnie planujemy mieć nazwę Strings. Ale moglibyśmy z łatwością zmienić nazwy na liczby całkowite, ponieważ przy 1000 produkcjach będziemy mieli nazwy zawierające więcej niż 4 znaki (które zakładam, że to 32 bity?). Jak Haskell sobie z tym radzi. Czy liczba Int zawsze jest 32-bitowa, a liczba całkowita przydziela pamięć, której tak naprawdę potrzebuje?
Przeczytałem również to: Opracowując test wartości / referencji semantyki Haskella - ale nie mogę zrozumieć, co to dla nas dokładnie znaczy - jestem bardziej imperatywnym dzieckiem Javy niż dobrym programistą: P