4. Der funktionale Ansatz

[ XML und Haskell Seminar ] ... [ Thema XML Verarbeitung mit Haskell ] ... [ 5. Vergleich mit bekannten Verfahren ]

Übersicht

4.1. Einleitung

Dr.Malcome Wallace und Colin Runciman haben das Tool "HaXML" entwickelt, welches mit Haskell realisiert wurde und sich die Mechanismen der Funktionalen Programmierung zu nutze macht. Das HaXML-System beeinhaltet zum Beispiel die 'irish composition' (o), einen Combinator welche eine Funktion auf das Ergebnis einer anderen Funktion anwendet. Genau auf die gleiche Art, wie Pipes das Ergebnis eines Programms auf ein weiteres Programm anwenden. In HaXML gibt es eine Vielzahl solcher Funktionsverbindungen, welche die Ergebnisse von mehreren Funktionen verknüpfen oder dazu benutzt werden aus dem Ergebnis einer Funktion bestimmte Eigenschaften zu selektieren.
Raffiniert an diesen Kombinatoren ist, dass es eigentlich nur Funktionen sind, welche in Haskell definiert sind. Diese Tatsache erlaubt es jedem neue, notwendig Kombinatoren zu erstellen und der Library hinzuzufügen.

4.2. Vorgehensweise

  1. Entwurf einer internen Datenstruktur, welche den Inhalt jedes beliebigen XML Dokuments abbilden kann.
  2. Definieren von Prädikaten, Selektoren und Konstruktoren, um Aussagen über ein bestehendes Dokument machen zu können, bzw. um ein Dokument entsprechend der aufgestellten Datenstruktur erzeugen zu können.
    Prädikate
    Selektoren
    Konstruktoren
  3. Entwurf einer Library von Kombinator-Operatoren, wobei es darum geht mehrere Funktionen zu einer Funktion zusammenzusetzen. Diese Library soll alle Funktionalitäten zur Verfügung stellen, welche zum Traversieren von Bäumen notwendig sind. Hierbei sollen die mathematischen Funktionalitäten (Konjunktion, Disjunktion, Negation) in den Vordergrund gestellt werden.

4.3. Die Datenstruktur

Wie schon erwähnt lassen sich Baumstrukturen in funktionalen Programmiersprachen intuitiv rekursiv abbilden. In Haskell ist es nicht notwendig sich mit Zeigern und Speicherallokation zu befassen. Rekursive Strukturen (z.B. Bäume) werden als rekursive algebraische Datentypen mit mehreren alternativen Konstruktoren definiert.
  1. Es muss ein Datentyp geschaffen werden, der die Struktur des XML-Baumes wiedergibt.
    data Element = ... .
     (data ist ein Schlüsselwort zur Definition von algebraischen Datentypen.)
  2. Die verschiedenen Daten in ihren Typen unterscheiden. Jede Art wird durch einen Konstruktor bestimmt. Konstruktoren dürfen in patterns auftreten und erlauben so die Definition von Funktionen über den Datentyp.
    XML-Dokument: Datei, welche die Dokumentdaten enthält. Üblicherweise wird dieses durch aussagekräftige XML-Elemente, von denen einige auch zusätzliche Informationen (Attribute) enthalten können, beschrieben. Ein Element besteht aus zwei Tags, einem öffnenden Start-Tag, das den Names des Elements zwischen einem Kleiner-Zeichen und einem Grösser-Zeichen einschliesst, und einem schliessenden Ende-Tag, das bis auf einem Slash, der vor dem Elementnamen steht, mit dem Start-Tag identisch ist. Der Text zwischen den Tags wird als Teil des Elements betrachtet und wird als Inhalt (Content) des Elements beschrieben.
    Attribute werden innerhalb des Start-Tags angegeben.

    data Element = Elem ...

    data Content = CElem ...
    | CRef ...
    | CMisc ...
    | CText ...
    ...
    Content ist ein Alternativer Datentyp, d.h. es gibt mehrere Möglichkeiten ein Element vom Typ Content zu erzeugen.
    Die Alternativen werden durch '|' getrennt.
  3. Für jeden Konstruktor müssen nun die Komponenten/Argumente bestimmt werden. Element ist ein Produkttyp, da er sich aus mehreren Komponenten zusammensetzt.

    data Element = Elem Name [Attribute] [Content]

    Um ein Element vom Typ Element zu erzeugen wird mindestens ein Name benötig, möglich sind Attribute und Content. Elem kann nun als pattern auf der linken-Seite einer Definition verwendet werden. Alternativ hätte hier auch ein Tupel verwendet werden können:

    type Element = (Name, [Attribute], [Content])
    Nachteile hierbei sind:
    • es fehlt ein explizites Label, welches den Zweck der Komponente beschreibt.
    • es können beliebige Paare erzeugt werden, die auf diesen Datentyp passen, auch wenn nicht wirklich ein Element gemeint ist. In der anderen Alternative müssen Elemente über den Konstruktor erzeugt werden.
    • der Typ ist nicht Gegenstand von Fehlermeldungen.
    Vorteil wäre:
    • der Datentyp wäre kompakter/kürzer.
    • für Tupel sind eine Anzahl polymorpher Funktionen definiert, die könnten uneingeschränkt verwendet werden.

    Der Inhalt (Content)
    data Content = CElem Element
    | CRef Reference
    | CMisc Misc
    | CText String
    ...
    Mit Hilfe von Typsynonymen können Namen für Typausdrücke eingeführt werden.

    type Attribute = (Name, AttValue)
    Typsynonyme werden verwendet, um `große' Typausdrücke abzukürzen und um die Lesbarkeit des Programms durch Verwendung aussagekräftiger Typnamen zu erhöhen. Bei Attribute handelt es sich um ein Tupel aus Name und AttValue. Tupel werden benutzt, um eine feste Zahl von Werten unterschiedlichen Typs zusammenzufassen
    data Misc = CComment Comment
    | PI ProcessingInstruction

    type Name = String
    data AttValue = AttValue [Either String Reference]
    type Reference = String
    type Comment = Comment
    type ProcessingInstruction = (PITarget,String)
    type PITarget = String
    ... .

Auch Korrektheitsbeweise orientieren sich an der Datentypdefinition.
Der Nachweis der Korrektheit erfolgt induktiv über die Struktur des Datentyps.
Nicht rekursive Konstruktoren ergeben Basisfälle, rekursive Konstruktoren werden induktiv behandelt.

4.4. CFilter-Datentyp

type CFilter = Content -> [Content]
CFilter wird somit zum Synonym. Allein angewendet bedeutet es, dass ein Content in eine Contentliste transformiert wird.

Es werden einige Funktionen benötigt, um "Teile" von eingelesenen Dokumenten zu verarbeiten, und andere um "Teile" für Dokumente zu erzeugen.
All diese Funktionen/Filter werden auf den gleichen Basistyp CFilter aufgebaut. Dies ist notwendig, wenn man sich die Möglichkeit offen halten möchte möglichst viele von den entwickelten Funktionen zu kombinieren.
Wird ein neues Dokument erzeugt, dann geht es häufig darum Teile/Informationen aus einem alten Dokument mit zu verarbeiten. Es ist also erforderlich, dass die Kombination derartiger Funktionen ermöglicht wird.
Das Ergebnis einer solchen Filterfunktion ist entweder leer, besteht aus genau einem Eintrag oder liefert auch mal eine Liste von Teilbäumen zurück.
Kommt es zu Mehrdeutigkeiten muss entschieden werden, ob der Eintrag verarbeitet werden soll, oder nicht.

4.5. HaXML

Mit HaXmL steht für eine Sammlung von Haskell-Programmen zur Verarbeitung von XML-Dokumenten zur Verfügung. Hierzu gehören ein Parser für XML, eine spezieller Parser für HTML und ein Pretty-Printer zur Ausgabe von XML-Dokumenten.
Darüber hinaus bietet HaXmL zwei Ansätze, um Dokumente zu verarbeiten. Der erste Ansatz verwendet eine allgemeine Baumstruktur zur Darstellung von XML-Dokumenten.
Zur Verarbeitung der XML-Bäumen wird eine Kombinator-Bibliothek bereitgestellt, die deren einfache Auswahl, Generierung und Transformation erlaubt. Der zweite Ansatz übersetzt XML-DTDs in algebraische Datentypen für Haskell mit entsprechenden Ein- und Ausgabefunktionen, er ist jedoch nicht Bestandteil diese Ausarbeitung.

Prädikate, Selektoren und Konstruktoren

Zunächst werden in HaXML eine Vielzahl von 'basic filtering functions' definiert. Hierbei handelt es sich um Prädikate, Selektoren und Konstruktoren. Mit Hilfe der Prädikate können klassifizierende Aussagen über ein XML Dokument erlangt werden. Beispiele:

Prädikat

Beschreibung

elm

liefert den Input zurück, wenn es sich um ein XML Element handelt.

none

nimmt den Input und gibt nichts zurueck

keep

nimmt den Input und gibt den Input zurueck (Identität)

txt

liefert den Input zurueck, wenn es sich um simplen Text handelt

tag

nimmt das aktuelle Element und ueberprueft, ob der uebergebene String der Name des Elements ist.

attr

nimmt das aktuelle Element und ueberprueft, ob der uebergebene String der Name des Elementattributs ist.

 

 

Ein Prädikat ist Teil einer Aussage, der eine klassifizierende Eigenschaft beinhaltet.
Um klassifizierende Aussagen über die Eigenschaften der Daten eines XML-Dokuments sowie über dessen Struktur zu machen werden Prädikate benötigt.
Der funktionale Ansatz weicht etwas von der gängigen Aussagenlogik ab.
Prädikate liefern meist Wahrheitswerte zurück, aufgrund der Tatsache, dass die Funktionen kombiniert werden sollen, werden auch die Prädikate an den Basistyp CFilter angelehnt. Die Wahrheitswerte werden folglich nur simuliert.
Eine Aussage, die keine Ergebnismenge zurückliefern würde liefert nicht FALSE sondern die leere Menge zurück.
Eine Aussage, die eine gültige Ergebnismenge liefert, liefert nicht TRUE zurück, sondern eine Ergebnisliste, angelehnt an CFilter.

An die Mathematik angelehnt soll nun die Nullfunktion und die Identitätsfunktion für den Datentyp beschrieben werden.
Um mehrere Aussagen kombinieren zu können ist es wichtig ein neutrales Element für den Inhalt und eine Identität für den Inhalt zur Verfügung zu stellen.

none :: CFilter
none = \x -> []
none liefert für jeden Content die leere Liste zurück. Es kann für Fehlerfälle oder Abbruchkriterien verwendet werden. Bei gewissen Verknüpfungen wird das Ergebnis nicht weiter verändert.

keep :: CFilter
keep = \x -> [x]
 keep liefert den unveränderten Content zurück. Es kann für Prüfungen verwendet werden, die im Erfolgsfälle den unveränderten Content zurückliefern.
Werden beispielsweise mehrere Suchkriterien kombiniert, dann wird bei jedemKriterium immer auf dem Ursprungsdaten und nicht auf gefilterten Daten gearbeitet.
none und keep bilden die Null- und Identitätsfunktion der Algebra ab.

elm :: CFilter
elm x@(CElem _ ) = [x]
elm _ = []
 elm wird mit einem Content "XML-Baum-Inhalt" aufgerufen. Handelt es sich bei dem Inhalt um ein Element, dann wird das Element zurückgeliefert, handelt es sich nicht um ein Element sondern um eine Referenz oder simplen Text dann wird die leere Liste zurückgeliefert.
Gemäss der Aussagenlogik wird folglich TRUE und FALSE zurückgeliefert.
Mit Hilfe der Konstruktoren findet das 'pattern matching' Anwendung.
Diese Funktionalität wird in den Funktionen txt, tag, attr, attrval ebenfalls umgesetzt.
Man benötigt diese Funktionen um Filter auf bestimmte Fragmente des Dokuments abzugrenzen.


Selektoren

Beschreibung

children

liefert die Kindelemente des Inputs zurück, wenn es sich beim Input um ein XML Element mit Kindelemente handelt

showAttr

liefert den Wert des angefragten Attributs zurück. Mit showAttr können auch mandatory Attribute überpüft werden.

Selektoren bilden immer vollständige Elemente genau einer Relation ab. Es wird folglich von einem Vaterknoten auf die Kindknoten durchgegriffen.
Generell bilden die in einem Element geschachtelten Kindelemente diese Relation ab, aber auch die Attribute (Attributliste) eines Elements können als abhängige Relation betrachtet werden.
Es werden also zwei Arten von Selektoren benötigt, beschrieben sei hier nur die Vater-Kind-Relation:
children :: CFilter children (CElem (Elem _ _ cs)) = cs children _ = []
 children liefert alle Kindelemente eines Elements (Ausgangsknoten).

Mit Hilfe von Konstruktoren können XML Elemente erzeugt und manipuliert werden.
Beispiele:

Konstruktor

Beschreibung

literal,(!)

Erzeugt simplen Text

mkElem

Erzeugt aus einem Inputstring ein XML Element.
Zur Erzeugung eines XML Dokument wird dieser Konstruktor sukzessive aufgerufen.

mkElemAttrs

Erzeugt aus Inputstring und einer Attributliste ein XML Element mit Attributen

replaceTag

Ersetzt ein XML Element mit Hilfe eines Inputstrings

replaceAttrs

Ersetzt die Attributliste eines Elements


mkElem :: String -> [CFilter] -> CFilter
mkElem h cfs = \t-> [ CElem (Elem h [] (cat cfs t)) ]
mkElem erzeugt ein neues Element. Des weiteren nimmt mkElem eine Liste von Filtern entgegen, welche auf ein Dokumentbaum angewendet werden.
Die Resultatmenge wird zu den Kindelementen des neuen Knoten. Folglich wird ein XML-Baum, welcher mit mkElem aufgebaut wird von den Blättern zur Wurzel hin entwickelt. Jedes neue Element, mit mkElem erzeugt, wird zum neuen Wurzelelement.
Soll ein neues Dokument erzeugt werden, dann wird mkElem wiederholt aufgerufen. Da mkElem eine Liste von Filtern erwartet muss zum Erzeugen eines neuen Baums immer etwas vom Typ Content zur Verfügung stehen. Es macht also Sinn sich einen leeren Content zu erzeugen, welcher zum initialisieren von neuen Dokumenten herangezogen werden kann.

mkElemAttr :: String -> [(String,String)] -> [CFilter] -> CFilter
mkElemAttr h as cfs = \t-> [ CElem (Elem h as(cat cfs t)) ]
 Soll ein neues Element mit Attributen versehen werden, dann wird dieses mit mkElemAttr erzeugt. mkElemAttr funktioniert wie mkElem nur das zusätzlich noch eine Attributliste der Funktion übergeben werden kann.

replaceTag :: String -> CFilter
replaceTag n (CElem (Elem _ _ cs)) = [CElem (Elem n [] cs)]
replaceTag n _ = []
 Mit replaceTag wird das aktuelle Tag (Elementname) umbenannt. Der übergebene String wird zum neuen Tag (Elementnamen).

replaceAttrs :: [(String,String)] -> CFilter
replaceAttrs as (CElem (Elem n _ cs)) = [CElem (Elem n as' cs)]
 Mit replaceAttrs werden Attributnamen und Werte umdefiniert.


Kombinatoren

Schliesslich wird eine 'Combinator library' definiert, in welcher die 'basic filter' auf unterschiedlichste Art und Weise verdrahtet werden. Voraussetzung für diese Verzahnung sind möglichst identische Funktionstypen. Wenn das Ergebnis einer Funktion in eine zweite, dritte etc. Funktion weitergeleitet werden soll geht dies nur, wenn die Typen (Ergbnis, Argument) identisch sind! Bei Kombinatoren handelt es sich um 'higher-order' Funktionen, welche die Basis für starke Funktionen liefern, in denen die Operatoren zusammengeführt werden können. In Haskell können dann auch neue 'infix operator symbols' für Kombinatoren eingeführt werden.
Wenn verschiedene Anfragen kombiniert werden sollen, dann geht es meist darum UND- oder ODER-Anfragen zu stellen.
Angelehnt an die Mathematik sollen die wichtigesten Verknüpfungen vorgestellt werden.

Diese Verknüpfungen werden in Haskell umgesetzt.

Beispiele:

Kombinatoren

Beschreibung

o irish compos.

Verkettet 2 Filter miteinander. Der Linke Filter wird auf das Resultat des Rechten angewandt.
z.B.> text ‘o’ children ‘o’ tag “title”

f (|||) g

vereinigt die Ergebnisse zweier Filter sequenziell.

f with g

Laesst fuer den Filter f nur diejenigen uebrig, fuer die auf Filter g gilt.

f without g

Schliesst fuer den Filter f diejenigen aus, die auf fuer den Filter g gueltig sind.

(/>)

 Interior Search; liefert die innere Struktur.

(</)

 Exterior Search; liefert die äussere Struktur.

f (|>|)g

Gibt entweder das Ergebnis von f zurueck, oder das Ergebnis von g, wenn f fehlschlaegt.

cat fs

||| fuer Listen. Verkettet die Ergebnisse der einzelnen Filter (fs ist eine Liste von Filtern)

deep f

Rekursive Transformation; f wird auf jedes Element des Baumes angewandt. Ist f erfolgreich, dann wird die Verarbeitung abgebrochen, ansonsten wird f auf das nächste Element des Baumes angewandt.
Der Baum wird nach dem Prinzip ‘Links-Rechts-Tiefendurchlauf’ durchlaufen.(top down)

deepest f

siehe deep; ‘Rechts-Links-Höhendurchlauf’. (bottom up)

multi f

Liefert alle Uebereinstimmungen zurück

foldXML f

Wendet den Filter f auf jeden Knoten des Baumes an bis die Wurzel erreicht ist.


Einer der nützlichsten und wichtigsten Kombinatoren ist die irish composition 'o'.
Dieser Kombinator verküpft zwei Filter miteinander. Das Ergebnis des linken Filters wird auf einen zweiten Filter (den rechten Filter) angewendet.
Auf diese Weise können zwei Constraints UND-verknüpft werden.
Die 'irish composition' ist folgendermassen definiert:

o :: CFilter -> CFilter -> CFilter
f 'o' g = concat . map f . g
o combiniert also zwei Funktionen.
Die Funktion g wird auf einen XML-Baum angewandt und liefert eine Ergebnisliste zurück. Mit Hilfe der map Funktion wird die Funktion f auf jedes Element der Ergebnisliste angewandt. f selbst liefert ja nun für jedes Element der Ergebnisliste ein Resultat vom Typ Liste. Die einzelnen Ergebnisse (Listen) werden dann konkateniert, so das letztendlich ein Resultat vom Typ Liste entsteht.

Beipiel:
o children ((multi.tag) "SIGN") a
->[CElem (Elem "HELP" [("name=","Haskell")] [])]
 multi.tag "SIGN" liefert eine Liste aller Elemente, deren Elementname "SIGN" ist. Auf diese Ergebnismenge wird der Selektor children angewendet, somit werden alle Kindelemente von SIGN Elementen zurückgeliefert.

Ein Such-Algorithmus sollte es auch erlauben einen Suchvorgang mit unterschiedlichen Contraints sequentiell zu starten, wo eine Ergebnismenge zurückgeliefert wird, die sich aus den Ergebnissen der einzelnen Suchläufe ergibt. (append results)

(|||) :: CFilter -> CFilter -> CFilter
f (|||) g = \c -> f c ++ g c

Beipiel:
(|||) (o children ((multi.tag) "SIGN" )) (o children ((multi.tag) "LANG")) a
-> [CElem (Elem "HELP" [("name=","Haskell")] []),CElem (Elem "HELP" [] [])]
 Zunächst werden alle Kindelemente von "SIGN" gesucht, dann alle Kindelemente von "LANG". Die Ergebnismenge konkateniert.
Kombiniert die Operatoren 'o' (|||) kann man aus jeden Dokument eine beliebige Ergebnismenge erausziehen, aus der man dann sogar ein neues Dokument aufbaut.


Ein Such-Algorithmus sollte mit einer beliebigen Anzahl von Filtern losgeschickt werden können und sobald eines der Filter ein gültiges Ergebnis liefert die weitere Suche beenden. Ein solcher Suchvorgang kann durch eine ODER-Verknüpfung von Constraints beschrieben werden. (direct choice)
(|>|) :: CFilter -> CFilter -> CFilter
f |>| g = \x-> let fx = f x in if null fx then g x else fx
 Mit Hilfe von let können Einmalzuweisungen vorgenommen werden. Die Funktion f wird auf ein XML-Dokument angewendet. Liefert die Funktion ein Ergebnis, dann wird die weitere Verarbeitung eingestellt. Liefert die Funktion kein gültiges Ergebnis, dann wird das Ergebnis der zweiten Funktion zurückgeliefert.

Beipiel:
(|>|) keep none a == (|>|) none keep a


with :: CFilter -> CFilter -> CFilter
f `with` g = filter (not.null.g) . f
 with kann als Wächter (guard) bezeichnet werden. Zunächst wird die Funktion f auf ein XML-Dokument angewendet. Für die Ergebnisliste wird überprüft, ob sie auch der Funktion g genügen. Liefert g NOT NULL dann liegt ein gültiges Ergebnis vor, ansonsten wird das Ergebnis vernachlässigt.

without :: CFilter -> CFilter -> CFilter
f `without` g = filter (null.g) . f
 without kann als negativer W&ächter verstanden werden. Mit without können Negationen formuliert werden. Die Funktion f wird angewendet. Auf die Ergebnismenge wird die Funktion g angewendet. Gültige Ergebnisse sind die, welche g nicht genügen.

Beispiele:
with (attr "name=") (tag "DOKUMENT") a

without (attr "name=") (tag "DOKUMENT") a
Zunächst wird das aktuelle Element auf den Tagnamen "DOKUMENT" geprüft. Dann wird geprüft, ob das Element ein Attribut mit dem Namen "name=" hat. Bei with muss das Ergebnis beiden Anfragen genügen, bei without darf das Element "DOKUMENT" kein Attribut "name=" haben.
Mit Hilfe der Negation können nun ganze Dokumentteile aus einem Dokument ausgeschlossen werden. Mit der Ergebnismenge könnte man ein neues Dokument erzeugen.

Pfad Selektoren sind wichtig, um gewisse Strukturen in einem Dokument zu prüfen, oder zu selektieren. Mit Hilfe der Pfad Selektoren können Vaterobjekte selektiert werden, die gewisse Eigenschaften erfüllen. Des weiteren werden die Eigenschaften der Kindelemente geprüft. Je nachdem, ob das Vaterelement für eine weitere Verarbeitung zur Verfügung stehen soll oder nicht, wird ein Selektor gewählt, welcher entweder das Vaterelement vernachlässigt, oder beibehält.

Interior Search: (liefert die innere Struktur) Auf das aktuelle Element wird ein Filter angewendet, vom Ergebnis werden die Kindelemente selektiert. Die Kindelemente werden durch eine zweite Funktion geschickt, das Ergebnis liefert die innere Struktur des Ausgangselements, welche den beiden Filtern f und g gerecht werden. Der Ausgangsknoten ist nicht weiter von Bedeutung. Der Erfolg der Selektion an den Kindern des Ausgangsknotens ist relevant für die Ergebnismenge.

f'o'g = concat . map f . g
(/>) :: CFilter -> CFilter -> CFilter
f /> g = g `o` children `o` f

Beispiel:
(/>) ((deep.tag) "SIGN") (attr "name=") a
[CElem (Elem "HELP" [("name=","Haskell")] [])]

 Exterior Seach: (liefert die äussere Struktur)
Für einen Ausgangsknoten, welcher der Funktion f gerecht werden muss, wird die weiterführende Struktur geprüft. Wird der Ausgangsknoten dieser Anforderung gerecht wird er als Ergebnis zurückgeliefert. Der Erfolg der Selektion am Ausgangsknoten ist relevant für die Ergebnismenge.

(</) :: CFilter -> CFilter -> CFilter
f </ g = f `with` (g `o` children )
 Die Funktion f wird auf ein XML Dokument angewendet. Dann wird für das Ergebnis überprüft, ob die Kindelemente einer zweiten Funktion g genügen. Letztendlich wird geprüft, ob das Ausgangselement eine gewisse Eigenschaft besitzt.
z.B. ob ein Ausgangselement keine Kindelement mehr besitzt.

Beispiel:
( -> [CElem (Elem "SIGN" [] [CElem (Elem "HELP"
[("name=","Haskell")] [])])]
 Zunächst wird das Element "HELP" im Dokument gesucht, dann geprüft, ob die Kindelemente von "HELP" Attribute "name=" besitzen.


Rekursion

Bisher wurden ausschliesslich Funktionen definiert, die sich auf ein Ausgangselement beziehen und maximal deren Kindelemente mit einbeziehen.
In den Beispielen wurde hin und wieder schon mal auf rekursive Funktionen zurückgegriffen, die an dieser Stelle näher betrachtet werden sollen.
Soll eine Baumstrukur traversiert werden, dann muss es möglich sein auf jede Ebene des Baumes ab- bzw. aufzusteigen. Da beim traversieren auch immer nach bestimmten Elementeigenschaften gesucht wird, scheint es sinnvoll rekursive Transformationen zu definieren, die auf jeder Ebene des Baumes ausgeführt werden können.
Folglich werden Kombinatoren benötigt, die eine gewisse/bereits definierte Filterfunktion auf jeden Bereich des Baumes ausführen lassen.
Einer solcher Kombinatoren ist deep f, der Filter f wird auf alle Teilbäume des aktuellen Knotens angewandt. (deep treibt somit den filter durch den Teilbaum, verläuft also Top-Down).
Sobald deep ein Ergebnis gefunden hat, welches auf den Filter passt, wird die Verarbeitung angehalten. deep liefert somit das erste gültige Ergebnis.

Eine Variation von deep ist deepest. deepest f arbeitet Bottom-Up, startet folglich vom untersten Element (rechts-unten) und arbeitet sich den Baum herauf.
Auch deepest beendet die Suche sobald ein gültiges Ergebnis gefunden worden ist.

multi f ist ein Kombinator, welcher alle gematchten Ergebnisse zurückliefert. Der Baum wird also vollständig durchlaufen. Das Resultat liefert eine Liste aller gültigen Ergebnisse des angewandten Filters.
Hier erfolgt der Durchlauf wieder Top-Down.

deep :: CFilter -> CFilter
deep f = f |>| (deep f `o` children)
deepest f = (deepest f `o` children) |>| f
multi f = (|||) f (multi f `o` children)

Beispiele:
 Zu guter Letzt soll noch ein sehr nützlicher Kombinator vorgestellt werden. Der Kombinator chip f verarbeitet die Kindelemente eines Ausgangselements. Auf die Kindelemente wird ein Filter angewendet, das Ergebnis dieses Filters ersetzt die Kindelemente des Ausgangsknotens.

chip :: CFilter -> CFilter
chip f (CElem (Elem n as cs)) = [CElem (Elem n as (concatMap f cs))]
chip f c = [c]
Beispiel:
chip (attr "name=") a
Es werden alle Elemente als Kindelemente des Ausgangsknoten eingefügt, welche ein Attribut "name=" besitzen.

Die vorgestellten Prädikate, Selektoren, Konstrukturen und Filter-Funktionen sind wichtige Funktionen, die Bestandteil von HaXML sind.
Hierbei handelt es sich nur um die Vorstellung einiger wichtiger Funktionen, in der Library selbst sind noch weitere nützliche Funktionen definiert, die hier nicht weiter vorgestellt werden sollen.
[ XML und Haskell Seminar ] ... [ Thema XML Verarbeitung mit Haskell ] ... [ 5. Vergleich mit bekannten Verfahren ]