-- an XML tree is empty, contains a single tag or a series of tags or
-- a content string
data XMLTree = Empty|
               Tag FTag|
               Tree [XMLTree]|
               Content Content

-- declaration of equality.
-- attention!!! the parents do not have to be equal!!
instance Eq XMLTree where
   Empty == Empty = True
   Tag (s, t, p) == Tag (s1, t1, p1) = (s == s1) && (t == t1)
   Tree [] == Tree [] = True
   Tree (x:xs) == Tree (y:ys) = (x == y) && (Tree xs == Tree ys)
   Content (s, p) == Content (s1, p1) = (s == s1) 
   t1 == t2  = False


-- the  string is the name of the tag (without attributes)
type STag = String  -- single tag (no attributes!!)
-- the first tree are the children; the second is the parent
type FTag = (STag, XMLTree, XMLTree) -- full tag
-- the XMLTree is the parent
type Content = (String, XMLTree)



-- walk a tree. The first input is the tree to walk.
-- The second input is a function that takes as input an XML tree
-- and as output an XML Tree. This function is applied to every
-- Tag or Content of the input tree and must return resp. Tag and Content.
-- The output tree is the modified input tree.
walkATree :: XMLTree -> (XMLTree -> XMLTree) -> XMLTree
walkATree Empty f = f Empty
walkATree (Tag tag) f = (Tag (s, (walkATree t f), p))
   where Tag (s, t, p) = f (Tag tag)
walkATree (Tree []) f = f (Tree [])
walkATree (Tree t@(x:xs)) f
   = merge (Tree [walkATree x f])  (walkATree (Tree xs) f)
walkATree c f = f c  -- content

-- select from a tree. The first input is the tree to select from.
-- The second input is a function that takes as input an XML tree
-- and as output an XML Tree. This function is applied to every
-- Tag or Content of the input tree and must return resp. Tag and Content.
-- The output tree is the concatenation of
-- the output from this function.
selectFromTree :: XMLTree -> (XMLTree -> [XMLTree]) -> [XMLTree]
selectFromTree Empty f = f Empty
selectFromTree (Tag tag@(s, t, p)) f  
   = (f (Tag tag)) ++ selectFromTree t f
selectFromTree (Tree t@(x:xs)) f
   = selectFromTree x f ++  (selectFromTree (Tree xs) f)
selectFromTree c f = f c  -- content

Example:

DB = selectFromTree tree f
     where f (Tag ("Verb", t, p)) = (Tag ("Var", t, p))
           f t = Empty

This example returns a list of tags where each "verb" tag is
replaced by a "Var" tag and all other tags are replaced
by empty.

data structure XML
===================

<?xml version="1.0"?>
<DB>
  <Term>
    <Subject>
    </Subject>
    <Subject>
      <URI>
        _T$$$1 _T$$$1
      </URI>
      <Verb>
        <URI>
          a http://www.w3.org/1999/02/22-rdf-syntax-ns#type
        </URI>
        <Object>
          <URI>
            :travelSchedule <danc#travelSchedule>
          </URI>
        </Object>
      </Verb>
      <Verb>
        <URI>
          :of <danc#of>
        </URI>
        <Object>
          <Term>
            <Subject>
              <URI>
                _T$$$2 _T$$$2
              </URI>
              <Verb>
                <URI>
                  a http://www.w3.org/1999/02/22-rdf-syntax-ns#type
                </URI>
                <Object>
                  <URI>
                    dc:author http://purl.org/dc/elements/1.1/author
                  </URI>
                </Object>
              </Verb>
              <Verb>
                <URI>
                  :of <danc#of>
                </URI>
                <Object>
                  <URI>
                    : <danc#>
                  </URI>
                </Object>
              </Verb>
            </Subject>
          </Term>
        </Object>
      </Verb>
    </Subject>
  </Term>
</DB>


Haskell Tag structure
=========================

type DB = [Tree]
data Tree = Subject Subject|
            Term Term|
            Empty

data Subject = Subject (Atom, [Verb])|
               Term Term

data Verb = Verb (Atom, [Object])|
            Term Term

data Object = Object Atom|
              Term Term

type Term = [Subject]

but how to write the methods walkATree and selectFromTree?


For example return all data Verb given a tree DB ??