Navigable trees

With type XML = Tree XMLNode, it is possible to access the children and descendants of a node, but not the ancestors or siblings. Module NTree provides a ``navigable tree'' data structure that can traverse up, left, and right as well as down the tree. It comes at the price of space-efficiency though: using an NTree instead of a Tree means that the entire document must be kept in memory and cannot be garbage-collected.

type NTree a = ... {- opaque -}
ntree		:: Tree a -> NTree a
subtreeNT	:: NTree a -> Tree a
dataNT  	:: NTree a -> a

The ntree function converts a Tree into an NTree. subtreeNT goes the other way, extracting the Tree value at the current node. dataNT returns the label of the current node; it is equivalent to treeRoot . subtreeNT.

Single-step navigation

upNT, downNT, leftNT, rightNT :: NTree a -> Maybe (NTree a)

upNT returns the parent of the input node; downNT returns the first child of the input node. leftNT (resp. rightNT) return the previous (resp. next) sibling node.

The return value for all four functions is Maybe (NTree a); they return Nothing if the input node is, respectively, the root, a leaf, or the first or last child of its parent.

Multi-step navigation

All of the principal XPath axes (excluding attribute::* and namespace::*) are provided:

ancestorAxis, ancestorOrSelfAxis, childAxis,
    descendantAxis, descendantOrSelfAxis,
    followingAxis, followingSiblingAxis, parentAxis,
    precedingAxis, precedingSiblingAxis, selfAxis
    :: NTree a -> [NTree a]