Portability | portable |
---|---|

Stability | stable |

Maintainer | Uwe Schmidt (uwe\@fh-wedel.de) |

Filter for n-ary tree structure with filter combinators copied and modified from HaXml (http://www.cs.york.ac.uk/fp/HaXml/)

Similar but more flexible functions for tree processing are defined in the arrow classes Control.Arrow.ArrowList, Control.Arrow.ArrowIf, Control.Arrow.ArrowTree and Control.Arrow.ArrowState. For new applications, especially for XML processing, it's recommended to use the arrow interface Text.XML.HXT.Arrow instead of this filter approach as part of the api Text.XML.HXT.Parser

- module Data.Tree.NTree.TypeDefs
- type TFilter node = NTree node -> NTrees node
- type TSFilter node = NTrees node -> NTrees node
- satisfies :: (a -> [b]) -> a -> Bool
- none :: a -> [b]
- this :: a -> [a]
- isOf :: (a -> Bool) -> a -> [a]
- isOfNode :: (node -> Bool) -> TFilter node
- mkNTree :: NTree node -> TFilter node
- replaceNode :: node -> TFilter node
- replaceChildren :: NTrees node -> TFilter node
- modifyNode :: (node -> Maybe node) -> TFilter node
- modifyNode0 :: (node -> node) -> TFilter node
- modifyChildren :: TSFilter node -> TFilter node
- substChildren :: TFilter node -> TFilter node
- processChildren :: TFilter node -> TFilter node
- o :: (a -> [b]) -> (c -> [a]) -> c -> [b]
- (.>) :: (a -> [b]) -> (b -> [c]) -> a -> [c]
- seqF :: [a -> [a]] -> a -> [a]
- (..>) :: (a -> [b]) -> (a -> b -> [d]) -> a -> [d]
- (+++) :: (a -> [b]) -> (a -> [b]) -> a -> [b]
- cat :: [a -> [b]] -> a -> [b]
- orElse :: (a -> [b]) -> (a -> [b]) -> a -> [b]
- iff :: (a -> [c]) -> (a -> [b]) -> (a -> [b]) -> a -> [b]
- choice :: [IfThen (a -> [c]) (a -> [b])] -> a -> [b]
- data IfThen a b = a :-> b
- when :: (a -> [a]) -> (a -> [a]) -> a -> [a]
- whenNot :: (a -> [a]) -> (a -> [a]) -> a -> [a]
- guards :: (a -> [b]) -> (a -> [b]) -> a -> [b]
- neg :: (a -> [c]) -> a -> [a]
- containing :: (a -> [b]) -> (b -> [c]) -> a -> [b]
- notContaining :: (a -> [b]) -> (b -> [c]) -> a -> [b]
- (/>) :: TFilter node -> TFilter node -> TFilter node
- (</) :: TFilter node -> TFilter node -> TFilter node
- deep :: TFilter node -> TFilter node
- deepest :: TFilter node -> TFilter node
- multi :: TFilter node -> TFilter node
- processBottomUp :: TFilter node -> TFilter node
- processBottomUpIfNot :: TFilter node -> TFilter node -> TFilter node
- processTopDown :: TFilter node -> TFilter node
- processTopDownUntil :: TFilter node -> TFilter node
- insertChildrenAt :: Int -> TFilter node -> TFilter node
- insertChildrenAfter :: TFilter node -> TFilter node -> TFilter node
- thisM :: Monad m => a -> m [a]
- noneM :: Monad m => a -> m [b]
- (.>>) :: Monad m => (a -> m [b]) -> (b -> m [c]) -> a -> m [c]
- seqM :: Monad m => [a -> m [a]] -> a -> m [a]
- (+++>>) :: Monad m => (a -> m [b]) -> (a -> m [b]) -> a -> m [b]
- catM :: Monad m => [a -> m [b]] -> a -> m [b]
- ifM :: Monad m => (a -> [b]) -> (a -> m [c]) -> (a -> m [c]) -> a -> m [c]
- choiceM :: Monad m => [IfThen (a -> [c]) (a -> m [b])] -> a -> m [b]
- whenM :: Monad m => (a -> m [a]) -> (a -> [b]) -> a -> m [a]
- whenNotM :: Monad m => (a -> m [a]) -> (a -> [b]) -> a -> m [a]
- guardsM :: Monad m => (a -> [b]) -> (a -> m [c]) -> a -> m [c]
- containingM :: Monad m => (a -> m [b]) -> (b -> [c]) -> a -> m [b]
- processChildrenM :: Monad m => (NTree node -> m [NTree node]) -> NTree node -> m [NTree node]
- processTopDownM :: Monad m => (NTree node -> m [NTree node]) -> NTree node -> m [NTree node]
- processBottomUpM :: Monad m => (NTree node -> m [NTree node]) -> NTree node -> m [NTree node]
- liftMf :: Monad m => (a -> [b]) -> a -> m [b]
- ($$) :: (a -> [b]) -> [a] -> [b]
- ($$<) :: Monad m => (a -> m [b]) -> [a] -> m [b]
- performAction :: Monad m => (a -> m b) -> a -> m [a]

# Documentation

module Data.Tree.NTree.TypeDefs

type TFilter node = NTree node -> NTrees nodeSource

tree filter type: a function mapping a tree onto a list of trees

filter can be used in various ways, as predicates, selectors, transformers, ...

satisfies :: (a -> [b]) -> a -> BoolSource

satisfies converts a result of a predicate filter into a boolean

is a shortcut for not . null

typical use in guards or ifs: `if (satisfies f) t then ... else ... `

- 1.parameter f : the predicate filter
- 2.parameter t : the tree to be tested
- returns :
`b = not (null (f t))`

# Filter

isOfNode :: (node -> Bool) -> TFilter nodeSource

select filter, selects trees with node values with a specific property

- 1.parameter p : the predicate for testing the node value
- returns :
`[]`

or`[t]`

depending on`p t`

a special case of `isOf`

filter

mkNTree :: NTree node -> TFilter nodeSource

filter for substituting an arbitray tree by a constant

- 1.parameter t : the result tree, the input tree is ignored
- returns : the filter

replaceNode :: node -> TFilter nodeSource

filter for replacing the node

- 1.parameter n : the new node
- returns : the editing filter

replaceChildren :: NTrees node -> TFilter nodeSource

filter for replacing the children

- 1.parameter cs : cs the list of children
- returns : the filter

modifyNode :: (node -> Maybe node) -> TFilter nodeSource

modifyNode0 :: (node -> node) -> TFilter nodeSource

filter for editing the node

- 1.parameter nf : the XNode editing funtion
- returns : the filter

modifyChildren :: TSFilter node -> TFilter nodeSource

filter for editing the children

all children are processed with a filter mapping lists to lists,
this enables not only elementwise editing by lifting a normal
filter to a list filter with `(f $$)`

(see '($$)') but also manipulation
of the order of the elements, e.g. reverse is an appropriate childen
editing function.

- 1.parameter csf : the children editing function
- returns : the filter

see also : `processChildren`

substChildren :: TFilter node -> TFilter nodeSource

filter for substituting the children of a tree by
a new list of childen computed by applying a filter to the input tree.
`modifyChildren`

can be expressed by `substChildren`

:
`modifyChildren f t`

is equal to `substChildren (f . getChildren)`

processChildren :: TFilter node -> TFilter nodeSource

Filter for editing the children of a tree element wise

- 1.parameter cf : the filter applied to the children
- returns : the editing filter

see also : `modifyChildren`

o :: (a -> [b]) -> (c -> [a]) -> c -> [b]Source

sequential composition of filters, usually written in infix notation f2 `o`

f1.

for predicate filter the logical AND

- 1.parameter f2 : the 2. filter
- 2.parameter f1 : the 1. filter
- returns : the fiter applying first f1 to n and then f2 to the result (like function composition)

(.>) :: (a -> [b]) -> (b -> [c]) -> a -> [c]Source

pronounced "followed by", defined as: `f .> g = g `o` f`

.

allows filter composition in a more readable way from left to right

- 1.parameter f1 : the 1. filter
- 2.parameter f2 : the 2. filter
- returns : the composition of f1 and f2

see also : `o`

, '(..>)'

seqF :: [a -> [a]] -> a -> [a]Source

apply a list of filters sequentially with '(.>)', for predicate filters the generalized AND

see also : '(.>)'

(..>) :: (a -> [b]) -> (a -> b -> [d]) -> a -> [d]Source

special sequential composition.

filter f is applied to an argument t. then filter g is applied to all elements of the result list, but the argument t is also passed as extra parameter to g.

This allows for step by step transformations of a tree with access to the original tree in every transformation step.

see also : '(.>)', `o`

(+++) :: (a -> [b]) -> (a -> [b]) -> a -> [b]Source

binary parallel composition, the logical OR for predicate filter

- 1.parameter f1 : the 1. filter
- 2.parameter f2 : the 2. filter
- returns : the filter for applying f1 and f2 both to an argument tree and concatenating the results

cat :: [a -> [b]] -> a -> [b]Source

apply a list of filters, a "union" for lists, for predicate filters the generalized OR

- 1.parameter fs : the list of filters
- returns : the composing filter

orElse :: (a -> [b]) -> (a -> [b]) -> a -> [b]Source

directional choice, usually written in infix notation as f `orElse`

g

- 1.parameter f : the 1. filter
- 2.parameter g : the 2. filter
- 3.parameter t : the tree
- returns : the filter, that applies f to t, if the result is not the empty list, the result is found, else g t is the result

iff :: (a -> [c]) -> (a -> [b]) -> (a -> [b]) -> a -> [b]Source

if then else lifted to filters

- 1.parameter p : the predicate filter
- 2.parameter t : the "then" filter
- 3.parameter e : the "else" filter
- returns : the resulting conditional filter

neg :: (a -> [c]) -> a -> [a]Source

negation lifted to filters

- 1.parameter f : the predicate filter
- returns : the filter, that succeeds, when f failed

containing :: (a -> [b]) -> (b -> [c]) -> a -> [b]Source

pruning: keep only those results from f for which g holds, usually written in infix notation as f `containing`

g

- 1.parameter f : the processing filter
- 2.parameter g : the predicate filter
- 3.parameter t : the tree
- returns : all trees r from f t, for which g r holds (is not the empty list)

see also : `notContaining`

notContaining :: (a -> [b]) -> (b -> [c]) -> a -> [b]Source

pruning: keep only those results from f for which g does not hold

see also : `containing`

(</) :: TFilter node -> TFilter node -> TFilter nodeSource

pronounced "outside" meaning f containing g

deep :: TFilter node -> TFilter nodeSource

top down search.

search terminates, when filter f succeeds can e.g. be used for finding all outermost tag node of a specific kind

deepest :: TFilter node -> TFilter nodeSource

bottom up search.

first the children are processed, if this does not succeed, the node itself is processed can e.g. be used for finding all innermost tag nodes of a specific kind

multi :: TFilter node -> TFilter nodeSource

process all nodes of the whole tree.

can e.g. be used for finding all nodes of a specific kind

processBottomUp :: TFilter node -> TFilter nodeSource

bottom up transformation

- 1.parameter f : the
*simple*transforming filter - returns : the filter that applies f to all subtrees and the tree itself in a deepth first left to right manner

see also : `processTopDown`

, `processBottomUpIfNot`

processBottomUpIfNot :: TFilter node -> TFilter node -> TFilter nodeSource

guarded bottom up transformation, stops at subtrees for which a predicate p holds

- 1.parameter f : the transforming filter
- 2.parameter p : the predicate filter for the guard
- returns : the filter for processing all (sub-)trees

see also : `processBottomUp`

processTopDown :: TFilter node -> TFilter nodeSource

top down transformation

- 1.parameter f : the
*simple*transforming filter - returns : the filter that applies f first to the tree and then recursively to all subtrees of the result

see also : `processBottomUp`

processTopDownUntil :: TFilter node -> TFilter nodeSource

top down transformation until a node to be transformed is found

- 1.parameter f : the
*simple*transforming filter - returns : the filter that applies f first to the tree and, if the filter does not succeed, recursively to all children of the input tree.

Example:

processTopDownUntil none

is the identity filter (maybe a bit more inefficient).

Example:

processTopDownUntil (add1Attr "border" "2" `containing` isTag "table")

is a filter for adding an attribute border="2" in all top level table tags. The content of table tags will remain unchanged.

see also : `processTopDown`

, `processBottomUp`

insertChildrenAt :: Int -> TFilter node -> TFilter nodeSource

insertion of trees into the list of children at a given position

useful for inserting something into the list of children at a given position
the list of children is split with the `splitAt`

function
the nodes are inserted between these two sublists.

examples: `insertChildrenAt 0 ins t`

inserts all elements computed with `ins t`

in front
of the childen of `t`

, `insertChildrenAt 1 ins t`

behind the first child

see also: `insertChildrenAfter`

insertChildrenAfter :: TFilter node -> TFilter node -> TFilter nodeSource

insertion of trees into the list of children after specific elements

useful for inserting something into the list of children of a node
the list of children is split with the `span`

function and the filter p as predicate
the nodes are inserted between these two sublists

examples: `insertChildrenAfter none ins t`

inserts all elements computed with `ins t`

in front
of the childen of `t`

, `insertChildrenAfter this ins t`

appends the elements to the children

see also: `insertChildrenAt`

# Monadic Filter

thisM :: Monad m => a -> m [a]Source

the monadic version of the identity filter this.

see also : `this`

(.>>) :: Monad m => (a -> m [b]) -> (b -> m [c]) -> a -> m [c]Source

sequential composition of monadic filters, monadic version of ".>".

- 1.parameter f1 : the 1. monadic filter
- 2.parameter f2 : the 2. monadic filter
- returns : the monadic fiter applying first f1 to n and then f2 to the result (like function composition)

see also : '(.>)'

seqM :: Monad m => [a -> m [a]] -> a -> m [a]Source

generalized sequential composition of monadic filters

ifM :: Monad m => (a -> [b]) -> (a -> m [c]) -> (a -> m [c]) -> a -> m [c]Source

monadic if-then-else.

- 1.parameter p : the predicate
- 2.parameter thenP : the then part: the monadic filter, that is applied if p holds for the input tree
- 3.parameter elseP : the else part
- returns : the monadic filter for the conditional

choiceM :: Monad m => [IfThen (a -> [c]) (a -> m [b])] -> a -> m [b]Source

monadic version of multiway branch. The list of cases `f :-> g`

is processed sequentially,
in the first case for that f holds g is applied, if no case matches, `noneM`

is
applied.
This filter can be used like a case expression: `choiceM [ p1 :-> f1, p2 :-> f2, ... , thisM :-> defaultFilter]`

containingM :: Monad m => (a -> m [b]) -> (b -> [c]) -> a -> m [b]Source

pruning: monadic version of containing, usually written in infix notation as f `containingM`

g

- 1.parameter f : the monadic processing filter
- 2.parameter g : the predicate filter
- 3.parameter t : the tree
- returns : all trees r from f t, for which g r holds (is not the empty list)

see also : `notContaining`

processChildrenM :: Monad m => (NTree node -> m [NTree node]) -> NTree node -> m [NTree node]Source

Filter for editing the children of a tree with a monadic filter

- 1.parameter cf : the monadic filter applied to the children
- returns : the monadic editing filter

see also : `processChildren`

processTopDownM :: Monad m => (NTree node -> m [NTree node]) -> NTree node -> m [NTree node]Source

monadic variant of `processTopDown`

processBottomUpM :: Monad m => (NTree node -> m [NTree node]) -> NTree node -> m [NTree node]Source

monadic variant of `processBottomUp`

liftMf :: Monad m => (a -> [b]) -> a -> m [b]Source

lift a filter to a monadic filter

- 1.parameter f : the
*simple*filter - returns : the lifted monadic version

($$) :: (a -> [b]) -> [a] -> [b]Source

infix operator for applying a filter to a list of trees

- 1.parameter f : the filter
- 2.parameter ts : the list of trees
- returns : the concatenated list of results

($$<) :: Monad m => (a -> m [b]) -> [a] -> m [b]Source

infix operator for applying a monadic filter to a list of trees, typically used in do-notation for processing of intermediate results.

- 1.parameter f : the monadic filter
- 2.parameter ts : the list of trees
- returns : the concatenated list of results

see also : '($$)'

performAction :: Monad m => (a -> m b) -> a -> m [a]Source

run an arbitray command on a tree t and return the tree, used for inserting arbitray commands in a filter pipeline

- 1.parameter cmd : the command
- 2.parameter t : the argument tree
- returns : the unchanged tree as a single element list