Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Deep Pattern Matching und Kompositionalität
Ich würde gerne meine Frage von heute morgen nochmal aufgreifen und fragen, ob/warum Deep Pattern Matching im Widerspruch zu Kompositionalität steht. Vielleicht übersehe ich ja etwas ganz Einfaches 
Siehe Folie 4-45:
Ich habe einen Syntaxbaum und definiere für eine Menge Γ pro Knotentyp t mit n >= 0 Kindern eine Funktion [m]Φ_t: Γ^n → Γ[/m], die die einzelnen Bedeutungen/Repräsentationen auf eine weitere Bedeutung abbildet.
Das gibt mir dann eine Abbildung [m]A: ST → Γ[/m] von einem Syntaxbaum in eine andere Repräsentation mit z. B. [m]Γ=Str[/m], die für n >= 0 so definiert ist:
A([X_1_{β_1}, X_2{β_2}, ..., X_n_{β_n}]_α) = Φ_t( A([X_1_{β_1}]), ..., A([X_n_{β_n}) )Das erinnert mich an einige Dinge aus der VL Theorie der Programmierung:
- der Syntaxbaum ist nichts anderes als ein induktiver Datentyp,
- und die Abbildung A kann äquivalent mittels eines folds über dem Datentyp definiert werden.
Insbesondere lässt sich jede primitiv rekursive Funktion damit definieren ([1], [2]), Deep Pattern Matching wäre wie folgt möglich:
Wähle die Zielmenge von A als [m]Γ’ = Γ x ST[/m] und definiere Φ_t mit
first(Φ_t(a_1, ..., a_n)) = /* wie gewünscht */
snd(Φ_t(a_1, ..., a_n)) = t_ctor(snd(a_1), ..., snd(a_n)),
wobei t_ctor der Konstruktor im induktiven Datentyp für den Knotentyp t ist. Nun kann ich in der ersten Zeile Deep Pattern Matching auf den Argumenten betreiben.
[1]: A tutorial on the universality and expressiveness of fold, S. 10
[2]: ThProg: inoffizielles Skript, S. 58