Funktionale Programmierung: XML DOM-Struktur in HXT

XmlTree

data NTree a  = NTree a [NTree a]     -- rose tree
 
data XNode    = XText String          -- plain text
              | ...
              | XTag QName XmlTrees   -- element name
                                      -- and list of attributes
              | XAttr QName           -- attribute name
              | ...
 
type QName    = ...                   -- qualified name
 
type XmlTree  = NTree XNode
 
type XmlTrees = [XmlTree]

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 allgemeiner Funktionstyp für alle Aufgaben
Filter	implementiert als List-Arrow
	newtype LA a b = LA { runLA : a -> [b] } type TreeFilter n = LA (NTree n) (NTree n) type XmlFilter = TreeFilter XmlTree
	Resultat eines Filters ist eine Liste von Ergebnissen (Bäumen)
	Einheitliche Schnittstelle für viele unterschiedliche Funktionsarten
Resultate
Prädikate	[] -- False (_:_) -- True
Selektion	[x] -- Selektion o.k., x enthält einen XText-Knoten [] -- Selektion nicht möglich
Editieren	[x] -- Verändern möglich [] -- Verändern nicht möglich
Löschen	[] -- Löschen o.k. [x] -- Löschen nicht möglich
Suchen	[] -- nichts gefunden [x] -- genau ein Resultat gefunden [x1,x2,...] -- mehrere Resultate gefunden
allgemein	[] -- False, undefined, nichts gefunden [x] -- Funktion, genau ein Resultat [x1,x2,...] -- Relation, mehrere Resultate

Null und Identität	none = arr $ const [] this = arr $ id
Allgemeiner Test
	isA :: (b -> Bool) -> LA b b isA p = LA $ \ x -> if p x then [x] else []
getNode, getChildren	Knotenattribut, alle Kinder, Selektor-Funktionen
	getChildren :: TreeFilter n getChildren = LA $ \ (NTree n cs) -> cs getNode :: LA (NTree n) n getNode = arr $ \ (NTree n cs) -> n
Knoten und Kinder transformieren	changeNode :: (n -> n) -> TreeFilter n changeNode f = arr $ \ (NTree n cs) -> NTree (f n) cs processChildren :: TreeFilter n -> TreeFilter n processChildren f = arr $ \ (NTree n cs) -> NTree n (concatMap (runLA f) cs)

Auswahl entweder - oder	orElse :: LA b c -> LA b c -> LA b c f `orElse` g = LA $ \ x -> let res = runLA f $ x in if null res then runLA g $ x else res
Verzweigung	if auf Filter angehoben
	iff :: LA b c' -> LA b c -> LA b c -> LA b c iff p f g = LA $ \ x -> if (not . null . runLA $ p) x then runLA f $ x else runLA g $ x
Verzweigung	einfache Varianten: when und guards
	when :: LA b b -> LA b c -> LA b b f `when` p = iff p f this guards :: LA b c -> LA b b -> LA b b 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 Knoten (top down)
	processTopDown :: TreeFilter n -> TreeFilter n processTopDown f = f >>> processChildren (processTopDown f)

XML DOM-Struktur in HXT

Haskell Datentypen zur Darstellung von XML

Verarbeitung

Wichtige elementare Filter und Kombinatoren