Überlagerungsdatenstruktur?

Question

Ich habe eine verschachtelte, gegenseitige rekursiv Datenstruktur, und möchte rechnerische teure Werte an einige der Knoten assoziieren. Eigentlich möchte ich die Blöcke in a vorübergehend verknüpfen Pandoc Dokument auf die Liste der Wörter, die in diesem Block auftreten.

Unattraktive Optionen, die ich vermeiden möchte:

• Erweitern Sie den Blockdatentyp so, dass er die Wortliste enthält, die auf das Erstellen eines neuen erweiterten Pandoc -Datentyps mit vielen (zerbrechlichen) Kesselplattencode hinausgeht

• Mapping -Blöcke zu Word -Listen; Das ist suboptimal, da die Blöcke zu komplex sind, um als Schlüssel effizient zu dienen

Die Richtung, in die ich eine Lösung suche, ist eine Art Überlagerungsdatenstruktur, die die erweiterten Blöcke enthält, aber mit den zugrunde liegenden Datentypen, so dass ich immer noch die umfangreichen Pandoc -Bibliotheken verwenden kann. Aber vielleicht ist dies nicht die Haskell -Denkweise ...

Post Scriptum 2011-06-12:

Wie die Kommentare zeigen, habe ich wahrscheinlich die Kosten des Kartenansatzes überschätzt, teilweise basierend auf falschen Annahmen. In der Tat: "Es gibt nichts täuschender als eine offensichtliche Tatsache".

Wie auch immer, ich akzeptiere die Antwort von Hammar, da sie zeigt, wie ein erweiterbarer Datentyp erstellt wird.

Vielen Dank

Answer 1

Sie können einen vorhandenen Datentyp nicht hinzufügen, wenn er nicht als erweiterbar ausgelegt wurde. Sie müssen sich daher auf eine externe Struktur wie a verlassen Map Um das Wort Listen mit jedem Block zu verknüpfen.

Wenn Sie jedoch den Datentyp ändern könnten, können Sie ihn durch Verallgemeinerung der Rekursion im Datentyp ausdehnen. Angenommen, Sie haben einen rekursiven Datentyp wie diesen:

data Tree = Leaf | Fork String Tree Tree

Wir können einen Parameter für die rekursive Verwendung von hinzufügen Tree:

data GenTree t = Leaf | Fork String t t

Um einen einfachen Baum wie das Original zu haben, nehmen wir den festen Punkt dieses Typs an:

data Fix a = Fix (a (Fix a))
type Tree = Fix GenTree

Jetzt können Sie den Typ mit zusätzlichen Daten an jeder rekursiven Site erweitern. Hier erfahren Sie, wie Sie einen Typ für beschriftete Bäume erstellen:

data Labelled t = Labelled Int (GenTree t)
type LabelledTree = Fix Labelled

strLength :: GenTree t -> Int
strLength Leaf = 0
strLength (Fork str _ _) = length str

label :: Tree -> LabelledTree
label (Fix tree) = Fix $ Labelled (strLength tree) (fmap label tree)

instance Functor GenTree where
    fmap f Leaf = Leaf
    fmap f (Fork s l r) = Fork s (f l) (f r)