Not logged in. · Lost password · Register

Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
433 posts
Subject: 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 Φ_t: Γ^n -> Γ, die die einzelnen Bedeutungen/Repräsentationen auf eine weitere Bedeutung abbildet.

Das gibt mir dann eine Abbildung A: ST -> Γ von einem Syntaxbaum in eine andere Repräsentation mit z. B. Γ=Str, 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 Γ' = Γ x ST 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
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen