3. Datenstruktur


[ Seminar "XML und Funktionale Programmierung" ] ... [ 2. Funktionale Programmierung mit Haskell ] ... [ 4. Verarbeitung mit Filtern ]

Übersicht


3.1. Einleitung

Die hierarchische Struktur von XML-Dokumenten wird meistens über Bäume dargestellt. Bäume lassen sich wiederum sehr einfach als verkettete Listen darstellen. Die funktionale Sprache Haskell ist geradezu dazu ausgelegt, Listen zu verarbeiten, was an den verschiedenen sehr hilfreichen Fähigkeiten von Haskell liegt.

Es gibt zwei grundsätzlich verschiedene Ansätze, XML-Dokumente darzustellen, wobei der generische Ansatz, das XML-Dokument in einer generischen Baumstruktur zu speichern, dieser Seminararbeit zu Grunde liegt. Dieser Ansatz wurde schon bei HXML verwendet, allerdings ist der von der Haskell XML Toolbox viel allgemeiner gehalten und damit auch flexibler einsetzbar. Ein detaillierter Vergleich der drei Ansätze von HaXML, HXML und der Haskell XML Toolbox wird in Kapitel 5 vorgestellt.


3.2. Der generische Datentyp, NTree

Der Datentyp der die generische Baumstruktur repräsentiert, ist der Datentyp NTree, der im gleichnamigen Modul definiert ist. NTree ist ein n-stelliger Baum, Rose-Tree genannt, also ein Knoten mit einer Liste von Kindelementen, welche wiederum Knoten sind. Knoten, die ein Blatt im Baum repräsentieren, enthalten eine leere Liste von Kindelementen. Das Typsynonym NTrees ist eine "Abkürzung" für eine Liste von Knoten und vereinfacht damit die Lesbarkeit und Programmierung. Mit Hilfe von Typsynonymen können Namen für Typausdrücke eingeführt werden. Diese beiden Typen bilden zusammen eine rekursive Datenstruktur.

Die Datenstruktur:
  data NTree node  = NTree node (NTrees node)
                     deriving (Eq, Ord, Show, Read)

  type NTrees node = [NTree node]

3.3. Der Datentyp XmlTree

Aufbauend auf den allgemeinen Datentyp NTree sind die beiden Typen XmlTree und XmlTrees, die Datentypen, die ein XML-Dokument als rekursive Baumstruktur definieren.

  type XmlTree  = NTree XNode

  type XmlTrees = NTrees XNode

Innerhalb des XML-Baumes können nur Daten vom Typ XNode gespeichert werden. Dieser Typ stellt alle logischen Elemente von XML dar. Zur Definition aller Elemente von XML werden noch einige Typsynonyme erzeugt.

  type Attributes = AssocList String String

Der Typ Attributes ist eine Liste von Elementen, die aus jeweils ein Paar aus Name und Wert besteht. Dazu wird der Datentyp AssocList verwendet, der hier nicht näher erläutert werden soll. Einige weitere Typen dienen zur Verbesserung der Lesbarkeit und des Verständnisses.

  type TagName  = QName

  type AttrName = QName

Der Datentyp QName, der hier verwendet wird, stellt die Namensräume (Namespaces) dar. Namensräume ermöglichen es, die Eindeutigkeit von XML-Elementen sicherzustellen und vermeiden Element-Kollisionen. Kollidierende Elemente sind solche, die den gleichen Namen besitzen, aber eine unterschiedliche Bedeutung haben. Der Unterschied in der Bedeutung tritt dann auf, wenn das XML-Dokument von zwei unterschiedlichen Anwendungen verarbeitet wird und zwei Elemente zufällig den gleichen Namen besitzen. Mit Hilfe von Namensräumen läßt sich das verhindern.

Beispiel: Namensraum-Definition
  <xsl:stylesheet xmlns:xsl='http://www.w3c.org/1999/XSL/Transform'>
    ...
  </xsl:stylesheet>

In diesem Beispiel wird der Namensraum für ein XSL-Stylesheet definiert. In dem Datentyp QName wird der Elementname dann wie folgt gespeichert:

  data QName = QN { namePrefix    :: String
                  , localPart     :: String
                  , namespaceUri  :: String
                  }
                  deriving (Eq, Ord, Show, Read)

Es wird also einmal das Präfix, wie z.B. 'xsl', der eigentliche Elementname und die Namensraum-URI gespeichert.

Der Typ XNode ist nun wie folgt definiert:

XNode:
  data XNode = XText String
              | XCharRef Int
              | XEntityRef String
              | XCmt String
              | XCdata String
              | XPi TagName XmlTrees
              | XTag TagName XmlTrees
              | XDTD DTDElem Attributes
              | XAttr AttrName
              | XError Int String
                deriving (Eq, Ord, Show, Read)

Mit Hilfe von "Pattern Matching" wird XNode so definiert, dass es jedes Element von XML - wie XCmt für die Kommentare, oder XText für einfachen Text - repräsentiert. XTag repräsentiert hierbei ein XML-Tag. Es besteht zum einen aus dem eben vorgestellten Typ TagName und zum anderen enthält es einen XmlTree. Dieser XmlTree enthält die Liste aller Attribute des XML-Tags. Sie werden auch als Baum abespeichert, in dem die Knoten vom Typ XAttr sind. In dem folgenden Beispiel wird dies noch deutlicher dargestellt. Auf alle Konstruktoren soll hier nicht eingegangen werden, lediglich XDTD soll im Folgenden genauer erklärt werden.


3.4. Der Datentyp DTDElem

Da XmlTree das gesamte XML-Dokument darstellen soll und damit auch mögliche Document Type Definitions (DTD), muss XNode auch die Fähigkeiten haben, DTD-Elemente zu speichern. Hierfür wird in XNode der Konstruktor XDTD aufgerufen, der ein Parameter vom Typ DTDElem erwartet. Für die Verarbeitung von DTD-Elementen wurde ein neuer algebraischer Datentyp erzeugt, da DTDs eine sehr komplexe Struktur inne haben.

DTDElem:
  data DTDElem = DOCTYPE
                | ELEMENT
                | CONTENT
                | ATTLIST
                | ENTITY
                | PENTITY
                | NOTATION
                | CONDSECT
                | NAME
                | PEREF
                  deriving (Eq, Ord, Show, Read)

3.5. Ein Beispiel

Das folgende Beispiel soll zeigen, wie ein einfaches XML-Dokument - bestehend aus einer DTD und dem XML-Baum - in dem Datentyp XmlTree gespeichert wird. Ein ähnliches Beispiel ist auch in der Haskell Xml Toolbox eingerichtet und kann mit dem Programm HXmlParser geparst werden.

Beispiel: Einfaches XML-Dokument
  <?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
  <!DOCTYPE a [
  <!ATTLIST a att1 CDATA #IMPLIED>
  <!ELEMENT a (b, c?)>
  <!ELEMENT b EMPTY>
  <!ELEMENT c (#PCDATA)>
  ]>

  <a att1="test">
    <b/>
    <c>Hallo Welt</c>
  </a>

Der folgende Graph zeigt die Darstellung als XmlTree. Die vordefinierten Entities wie amp etc. sind von dem Parser automatisch mit in die DTD übernommen worden. Desweiteren wurde der Knoten "/" hinzugefügt, so dass sowohl die DTD als auch das XML-Dokument in einem einzigen Baum zusammengefasst werden können. Die Whitespaces, Linefeeds etc. werden von dem Parser als extra XText-Knoten repräsentiert.

Beispiel: Einfaches XML-Dokument als XmlTree
---XTag "/"
   |   "trace"="4"
   |   "source"="seminar.xml"
   |   "status"="0"
   |   "message"="in getXmlContents"
   |   "transfer-Protocol"="file"
   |   "transfer-URI"="file://localhost/home/manuel/haskell/hxml/examples/hparser/seminar.xml"
   |   "transfer-Status"="200"
   |   "transfer-Message"="OK"
   |   "version"="1.0"
   |   "encoding"="UTF-8"
   |   "standalone"="yes"
   |   "transfer-Encoding"="UTF-8"
   |
   +---XPi "xml"
   |   |   "version"="1.0"
   |   |   "encoding"="UTF-8"
   |   |   "standalone"="yes"
   |
   +---XText "\n  "
   |
   +---XDTD DOCTYPE [("name","a")]
   |   |
   |   +---XDTD ENTITY [("name","lt")]
   |   |   |
   |   |   +---XText "&"
   |   |   |
   |   |   +---XText "#60;"
   |   |
   |   +---XDTD ENTITY [("name","gt")]
   |   |   |
   |   |   +---XText ">"
   |   |
   |   +---XDTD ENTITY [("name","amp")]
   |   |   |
   |   |   +---XText "&"
   |   |   |
   |   |   +---XText "#38;"
   |   |
   |   +---XDTD ENTITY [("name","apos")]
   |   |   |
   |   |   +---XText "'"
   |   |
   |   +---XDTD ENTITY [("name","quot")]
   |   |   |
   |   |   +---XText "\""
   |   |
   |   +---XDTD ATTLIST [("name","a"),("value","att1"),("kind","#IMPLIED"),("type","CDATA")]
   |   |
   |   +---XDTD ELEMENT [("name","a"),("type","children")]
   |   |   |
   |   |   +---XDTD CONTENT [("modifier",""),("kind","seq")]
   |   |       |
   |   |       +---XDTD NAME [("name","b")]
   |   |       |
   |   |       +---XDTD CONTENT [("modifier","?"),("kind","seq")]
   |   |           |
   |   |           +---XDTD NAME [("name","c")]
   |   |
   |   +---XDTD ELEMENT [("name","b"),("type","EMPTY")]
   |   |
   |   +---XDTD ELEMENT [("name","c"),("type","#PCDATA")]
   |
   +---XText "\n\n  "
   |
   +---XTag "a"
       |   "att1"="test"
       |
       +---XText "\n    "
       |
       +---XTag "b"
       |
       +---XText "\n    "
       |
       +---XTag "c"
       |   |
       |   +---XText "Hallo Welt"
       |
       +---XText "\n  "

Die Repräsentation des XML-Dokumenten-Teils stellt sich dann wie folgt dar:

Beispiel: Repräsentation des XML-Teils:
  NTree (XTag (QN {namePrefix = "", localPart = "a", namespaceUri = ""})         -- Wurzelknoten
    [NTree (XAttr (QN {namePrefix = "", localPart = "att1", namespaceUri = ""})) -- Attributliste
      [NTree (XText "test") []]])                                                -- Attributwert
    [
    NTree (XText "\n    ") [],
    NTree (XTag (QN {namePrefix = "", localPart = "b", namespaceUri = ""}) []) [],
    NTree (XText "\n    ") [],
    NTree (XTag (QN {namePrefix = "", localPart = "c", namespaceUri = ""}) []) [
      NTree (XText "Hallo Welt") []
    ],NTree (XText "\n  ") []
  ]

[ Seminar "XML und Funktionale Programmierung" ] ... [ 2. Funktionale Programmierung mit Haskell ] ... [ 4. Verarbeitung mit Filtern ]