Funktionale Programmierung: Beispiel: XML mit Haskell

1. Versuch	data XmlTree = -- leaves XText String \| XCmt String \| XPi ... \| XCharRef Int \| XEntityref String \| XCdata String -- inner nodes \| XElem ElemName ElemAttrl [XmlTree] \| XDTD ... type Elemname = String type AttrName = String type ElemAttrl = [(AttrName, String)]

	viele unterschiedliche Datentypen und Varianten
	viele umständlich zu kombinierende Funktionen zum Testen zum Selektieren zum Transformieren zum Vergleichen: DTD <--> Inhalt
	mehrere Hierachien: Inhalt und DTD
	mehrere Taversierungsroutinen

2. Versuch
Lösung	uniformes Datenmodell nur noch eine Hierarchie
	Rekursive Struktur (Baum) trennen von der Information an den Knoten
	n-stellige Bäume (Rose-Trees, Rhododendron-Bäume)
Rekursion	data NTree node = NTree node [NTree node] type XmlTree = NTree XNode
Knoten	data XNode = XText String \| XCharRef Int \| XEntityRef String \| XCmt String \| XCdata String \| XPi ElemName PiAttrl \| XElem ElemName ElemAttrl \| XDTD DTDElem Attributes \| XAttr AttrName \| XError Int String type ElemAttrl = XmlTrees type PiAttrl = XmlTrees type Attributes = [(String, String)] data DTDElem = DOCTYPE \| ELEMENT \| CONTENT \| ATTLIST \| ENTITY \| PENTITY \| NOTATION \| CONDSECT \| NAME \| PEREF

Konsequenzen
	Traversierungsroutinen können unabhänging vom Knotentyp implementiert werden
	DTD-Teil kann nach gleicher Strategie traversiert werden wie der Inhaltsteil
	Struktur flexibler als von XML gefordert
	Konsistenz der Daten bei der Verarbeitung beachten

einfache Funktionen	Knoten testen Teile eines Knotens selektieren Knoten oder Teile verändern
zusammengesetzte Funktionen	ganze Teilbäume testen Teilbäume selektieren Teilbäume verändern
Kombination	von beliebigen Tests, Selektionen, Manipulationen
	eingebettete problemspezifische Sprache
	DSL, Domain Specific Language, Kombinatoren-Bibliothek
	nur möglich bei einheitlichen Funktionstypen

typische Signaturen	test :: ... -> XmlTree -> Bool sel :: ... -> XmlTree -> String child :: ... -> XmlTree -> Maybe Tree edit :: ... -> XmlTree -> XmlTree search :: ... -> XmlTree -> [XmlTree]
	Wie soll mit Funktionen umgegangen werden, die nur auf einer bestimmten Knoten-Variante definiert sind, z.B. Selektion des Elementnamens bei Textknoten?

Lösung	ein Typ für alle Aufgaben
Filter	type XmlFilter = XmlTree -> [XmlTree]
	Resultat ist eine Liste von Bäumen
Resultate
Prädikate	[] -- False (_:_) -- True
Selektion	[x] -- selektion o.k., x enthält einen XText-Knoten [] -- selektion nicht möglich
Editieren	[x] -- edit möglich [] -- edit nicht möglich
Löschen	[] -- löschen o.k. [x] -- löschen nicht möglich
Suchen	[] -- nichts gefunden [x] -- genau einen Baum gefunden [x1,x2,...] -- mehrere Bäume gefunden
allgemein	[] -- False, undefined, nichts gefunden [x] -- Funktion, genau ein Resultat [x1,x2,...] -- Relation, mehrere Resultate

einfache allgemeine Filter
none	0-Filter
	none :: NTree node -> [NTree node] none t = []
this	Identität
	this :: NTree node -> [NTree node] this t = [t]
allgemeiner Test
	test :: (node -> Bool) -> NTree node -> [NTree node] test p t@(NTree n cs) \| p n = [t] \| otherwise = [] test p t@(NTree n cs) = if p n then this else none $ t
children	alle Kinder, eine Selektor-Funktion
	children :: NTree node -> [NTree node] children (NTree n cs) = cs
edit	edit :: (node -> node) -> NTree node -> [NTree node] edit f (NTree n cs) = [NTree (f n) cs]

Filter Kombinatoren
Filter Typ	viele sinnvolle Filter können allgemein und ohne Ausnutzung der Struktur der Knoten-Attribute entwickelt werden
	type TreeFilter n = NTree n -> [NTree n]
Komposition	2 Filter hintereinander anwenden
	(>>>) :: TreeFilter n -> TreeFilter n -> TreeFilter n f1 >>> f2 = \t -> concat [f2 t1 \| t1 <- f1 t] f1 >>> f2 = concat . (map f2) . f1 f1 >>> f2 = concatMap f2 . f1 p1 >>> p2 -- logisches UND für Prädikat Filter grandChildren = children >>> children
	Funktionskomposition, nur in Leserichtung von links nach rechts
Vereinigung	2 Filter "gleichzeitig" auf einen Baum anwenden
	(<+>) :: TreeFilter n -> TreeFilter n -> TreeFilter n f1 <+> f2 = \t -> f1 t ++ f2 t p1 <+> p2 -- logisches OR für Prädikat Filter
Auswahl entweder - oder	orElse :: TreeFilter n -> TreeFilter n -> TreeFilter n f `orElse` g = \ t -> let res = f t in if null res then g t else res
Verzweigung	if auf Filter angehoben
	iff :: TreeFilter n -> TreeFilter n -> TreeFilter n -> TreeFilter n iff p f g = \ t -> if (not . null . p) t then f t else g t
Verzweigung	einfache Varianten: when und guards
	when :: TreeFilter n -> TreeFilter n -> TreeFilter n f `when` p = iff p f this guards :: TreeFilter n -> TreeFilter n -> TreeFilter n p `guards` f = iff p f none
Suchen	top down aller Teilbäume mit einer Eigenschaft
	deep :: TreeFilter n -> TreeFilter n deep f = f `orElse` ( getChildren >>> deep f ) deep isTableElem -- alle äußeren Tabellen
Suchen	aller Teilbäume mit einer Eigenschaft
	multi :: TreeFilter n -> TreeFilter n multi f = f <+> ( getChildren >>> multi f ) multi isTableElem -- alle Tabellen
Modifizieren	aller Kindknoten
	processChildren :: TreeFilter n -> TreeFilter n processChildren f (NTree n cs) = [NTree n (concatMap f cs)]
Modifizieren	aller Knoten (top down)
	processTopDown :: TreeFilter n -> TreeFilter n processTopDown f t = f >>> processChildren ( processTopDown f)
URL umschreiben	rewriteURL :: XmlFilter rewriteURL = processTopDown ( rewriteHref `when` ( hasName "a" >>> hasAttr "href" )) where rewriteHref = ...
Anfragesprache	durch Kombination von Prädikaten und Baumtraversierung
Beispiel	Der Text aller H1-Überschriften in einem HTML-Dokument
	hasName "html" >>> getChildren >>> hasName "body" >>> getChildren >>> deep (hasName "h1") >>> getChildren >>> deep isText
Beispiel	XPath-Anfragen: `x/y/z//u/v`
	hasName "x" >>> getChildren >>> hasName "y" >>> getChildren >>> hasName "z" >>> getChildren >>> deep (hasName "u") >>> getChildren >>> hasName "v"
	(/>) :: TreeFilter n -> TreeFilter n -> TreeFilter n f /> g = f >>> getChildren >>> g hasName "x" /> hasName "y" /> hasName "z" /> deep (hasName "u") /> hasName "v"
DSL	Domain Specific Language (problemspezifische Sprache eingebettet in Haskell
	bewährte Technik
	flexibel, effizient
	1-1-Korrespondenz: Modell des Problembereichs <--> Programm
Voraussetzung	Konstruktion von eigenene problemspezifischen Kontrollstrunkturen

Beispiel: XML mit Haskell

XML: Bestandteile

XML Beispiel

Datenmodell

Verarbeitung