Oft muss ich einem ADT Felder hinzufügen, die nur einige redundante Informationen speichern. Aber ich habe nicht ganz herausgefunden, wie ich es gut und effizient machen soll.

Das Problem lässt sich am besten anhand eines Beispiels veranschaulichen. Angenommen, wir arbeiten mit nicht typisierten Lambda-Begriffen:

type VSym = String

data Lambda = Var VSym 
            | App Lambda Lambda
            | Abs VSym Lambda

Und von Zeit zu Zeit müssen wir die Menge der freien Variablen eines Terms berechnen:

fv :: Lambda -> Set VSym
fv (Var v)    = Set.singleton v
fv (App s t)  = (fv s) `Set.union` (fv t)
fv (Abs v t)  = v `Set.delete` (fv t)

Bald erkennen wir, dass wiederholte Berechnungen vonfv sind ein Engpass unserer Anwendung. Wir möchten es irgendwie zum Datentyp hinzufügen. Mögen:

data Lambda1 = Var (Set VSym) VSym
             | App (Set VSym) Lambda Lambda
             | Abs (Set VSym) VSym Lambda

Aber es macht die Definition ziemlich hässlich. Fast(Set VSym) nimmt mehr Platz als der ganze Rest. Darüber hinaus wird die Mustererkennung in allen verwendeten Funktionen aufgehobenLambda. Und um die Sache noch schlimmer zu machen, müssen wir später alle Muster neu schreiben, wenn wir uns dazu entschließen, ein anderes Memofeld hinzuzufügen.

Wie kann eine allgemeine Lösung entworfen werden, mit der sich solche Memofelder einfach und unauffällig hinzufügen lassen? Ich möchte folgende Ziele erreichen:

Dasdata Die Definition sollte dem Original so nahe wie möglich kommen, damit sie leicht lesbar und verständlich ist.Auch Musterübereinstimmungen sollten einfach und lesbar bleiben.Das spätere Hinzufügen eines neuen Memo-Feldes sollte den vorhandenen Code nicht beschädigen, insbesondere:bestehende Muster nicht zu brechen,keine Änderungen erforderlich machen, bei denen die zu merkende Funktion verwendet wurde (wie der verwendete Code)fv in diesem Beispiel).

Ich beschreibe meine derzeitige Lösung: Um diedata Definition und Muster stimmen so gut wie möglich überein. Definieren wir:

data Lambda' memo = Var memo VSym 
                  | App memo (Lambda' memo) (Lambda' memo)
                  | Abs memo VSym (Lambda' memo)
type Lambda = Lambda' LambdaMemo

wo die zu speichernden Daten separat definiert werden:

data LambdaMemo = LambdaMemo { _fv :: Set VSym, _depth :: Int }

Dann eine einfache Funktion, die den gespeicherten Teil abruft:

memo :: Lambda' memo -> memo
memo (Var c _)   = c
memo (App c _ _) = c
memo (Abs c _ _) = c

(Dies könnte durch die Verwendung von benannten Feldern beseitigt werden. Aber dann würden wirmüssen alle anderen Felder benennen auch.)

Auf diese Weise können wir bestimmte Teile aus dem Memo auswählen und dabei die gleiche Signatur von beibehaltenfv wie vorher:

fv :: Lambda -> Set VSym
fv = _fv . memo

depth :: Lambda -> Int
depth = _depth . memo

Schließlich deklarieren wir diese intelligenten Konstruktoren:

var :: VSym -> Lambda
var v = Var (LambdaMemo (Set.singleton v) 0) v

app :: Lambda -> Lambda -> Lambda
app s t = App (LambdaMemo (fv s `Set.union` fv t) (max (depth t) (depth s))) s t

abs :: VSym -> Lambda -> Lambda
abs v t = Abs (LambdaMemo (v `Set.delete` fv t) (1 + depth t)) v t

Jetzt können wir effizient Dinge schreiben, die Pattern Matching mit dem Lesen der gespeicherten Felder mischen

canSubstitute :: VSym -> Lambda -> Lambda -> Bool
canSubstitute x s t
  | not (x `Set.member` (fv t))
      = True -- the variable doesn't occur in `t` at all
canSubstitute x s t@(Abs _ u t')
  | u `Set.member` (fv s)
      = False
  | otherwise
      = canSubstitute x s t'
canSubstitute x s (Var _ _)
      = True
canSubstitute x s (App _ t1 t2)
      = canSubstitute x s t1 && canSubstitute x s t2

Dies scheint zu lösen:

Der Mustervergleich ist immer noch vernünftig.Wenn wir ein neues Memo-Feld hinzufügen, wird der vorhandene Code nicht gestört.Wenn wir uns entscheiden, eine Funktion mit Unterschrift zu merkenLambda -> Something Wir können es leicht als neues Memofeld hinzufügen.

Was mir an diesem Design immer noch nicht gefällt:

Dasdata Definition ist nicht so schlecht, aber immer noch platzierenmemo überall ist es erheblich überladen.Wir brauchen kluge Konstruktoren, um Werte zu konstruieren, aber wir verwenden die regulären Konstruktoren für den Mustervergleich. Das ist nicht so schlimm, wir fügen einfach einen hinzu_, aber die gleiche Signatur für das Konstruieren und Dekonstruieren zu haben, wäre schön. Schätze ichAnsichten oderMuster Synonyme würde es lösen.Die Berechnung der gespeicherten Felder (freie Variablen, Tiefe) ist eng an die intelligenten Konstruktoren gekoppelt. Es ist vernünftig anzunehmen, dass diese gespeicherten Funktionen immer vorhanden sein werdenKatamorphismenIch glaube, dies könnte zu einem gewissen Grad durch Tools wie gelöst werdendas Fixpoint-Paket.

Irgendwelche Ideen, wie man es verbessern kann? Oder gibt es bessere Möglichkeiten, um ein solches Problem zu lösen?