hxt-8.0.0: doc/hdoc/src/Control-Arrow-ArrowTree.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>Haskell Code by HsColour</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='comment'>-- ------------------------------------------------------------</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='comment'>{- |
<a name="line-4"></a> Module : Control.Arrow.ArrowTree
<a name="line-5"></a> Copyright : Copyright (C) 2005 Uwe Schmidt
<a name="line-6"></a> License : MIT
<a name="line-7"></a>
<a name="line-8"></a> Maintainer : Uwe Schmidt (uwe\@fh-wedel.de)
<a name="line-9"></a> Stability : experimental
<a name="line-10"></a> Portability: portable
<a name="line-11"></a> Version : $Id: ArrowTree.hs,v 1.12 2006/11/30 16:05:24 hxml Exp $
<a name="line-12"></a>
<a name="line-13"></a>List arrows for tree processing.
<a name="line-14"></a>
<a name="line-15"></a>Trees that implement the "Data.Tree.Class" interface, can be processed
<a name="line-16"></a>with these arrows.
<a name="line-17"></a>
<a name="line-18"></a>-}</span>
<a name="line-19"></a>
<a name="line-20"></a><span class='comment'>-- ------------------------------------------------------------</span>
<a name="line-21"></a>
<a name="line-22"></a><span class='keyword'>module</span> <span class='conid'>Control</span><span class='varop'>.</span><span class='conid'>Arrow</span><span class='varop'>.</span><span class='conid'>ArrowTree</span>
<a name="line-23"></a> <span class='layout'>(</span> <span class='conid'>ArrowTree</span><span class='layout'>(</span><span class='keyglyph'>..</span><span class='layout'>)</span>
<a name="line-24"></a> <span class='layout'>,</span> <span class='conid'>Tree</span>
<a name="line-25"></a> <span class='layout'>)</span>
<a name="line-26"></a><span class='keyword'>where</span>
<a name="line-27"></a>
<a name="line-28"></a><span class='keyword'>import</span> <span class='conid'>Data</span><span class='varop'>.</span><span class='conid'>Tree</span><span class='varop'>.</span><span class='conid'>Class</span> <span class='layout'>(</span><span class='conid'>Tree</span><span class='layout'>)</span>
<a name="line-29"></a><span class='keyword'>import</span> <span class='keyword'>qualified</span> <span class='conid'>Data</span><span class='varop'>.</span><span class='conid'>Tree</span><span class='varop'>.</span><span class='conid'>Class</span> <span class='keyword'>as</span> <span class='conid'>T</span> <span class='varid'>hiding</span> <span class='layout'>(</span><span class='conid'>Tree</span><span class='layout'>)</span>
<a name="line-30"></a>
<a name="line-31"></a><span class='keyword'>import</span> <span class='conid'>Control</span><span class='varop'>.</span><span class='conid'>Arrow</span>
<a name="line-32"></a><span class='keyword'>import</span> <span class='conid'>Control</span><span class='varop'>.</span><span class='conid'>Arrow</span><span class='varop'>.</span><span class='conid'>ArrowList</span>
<a name="line-33"></a><span class='keyword'>import</span> <span class='conid'>Control</span><span class='varop'>.</span><span class='conid'>Arrow</span><span class='varop'>.</span><span class='conid'>ArrowIf</span>
<a name="line-34"></a>
<a name="line-35"></a><span class='keyword'>infixl</span> <span class='num'>5</span> <span class='varop'>/></span><span class='layout'>,</span> <span class='varop'></</span>
<a name="line-36"></a>
<a name="line-37"></a><span class='comment'>-- ------------------------------------------------------------</span>
<a name="line-38"></a>
<a name="line-39"></a><span class='comment'>-- | The interface for tree arrows</span>
<a name="line-40"></a><span class='comment'>--</span>
<a name="line-41"></a><span class='comment'>-- all functions have default implementations</span>
<a name="line-42"></a>
<a name="line-43"></a><a name="ArrowTree"></a><span class='keyword'>class</span> <span class='layout'>(</span><span class='conid'>ArrowPlus</span> <span class='varid'>a</span><span class='layout'>,</span> <span class='conid'>ArrowIf</span> <span class='varid'>a</span><span class='layout'>)</span> <span class='keyglyph'>=></span> <span class='conid'>ArrowTree</span> <span class='varid'>a</span> <span class='keyword'>where</span>
<a name="line-44"></a>
<a name="line-45"></a> <span class='comment'>-- | select the children of the root of a tree</span>
<a name="line-46"></a>
<a name="line-47"></a> <span class='varid'>getChildren</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-48"></a> <span class='varid'>getChildren</span> <span class='keyglyph'>=</span> <span class='varid'>arrL</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>getChildren</span>
<a name="line-49"></a>
<a name="line-50"></a> <span class='comment'>-- | select the attribute of the root of a tree</span>
<a name="line-51"></a>
<a name="line-52"></a> <span class='varid'>getNode</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='varid'>b</span>
<a name="line-53"></a> <span class='varid'>getNode</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>getNode</span>
<a name="line-54"></a>
<a name="line-55"></a> <span class='comment'>-- | substitute the children of the root of a tree</span>
<a name="line-56"></a>
<a name="line-57"></a> <span class='varid'>setChildren</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='keyglyph'>[</span><span class='varid'>t</span> <span class='varid'>b</span><span class='keyglyph'>]</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-58"></a> <span class='varid'>setChildren</span> <span class='varid'>cs</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='layout'>(</span><span class='conid'>T</span><span class='varop'>.</span><span class='varid'>setChildren</span> <span class='varid'>cs</span><span class='layout'>)</span>
<a name="line-59"></a>
<a name="line-60"></a> <span class='comment'>-- | substitute the attribute of the root of a tree</span>
<a name="line-61"></a>
<a name="line-62"></a> <span class='varid'>setNode</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>b</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-63"></a> <span class='varid'>setNode</span> <span class='varid'>n</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='layout'>(</span><span class='conid'>T</span><span class='varop'>.</span><span class='varid'>setNode</span> <span class='varid'>n</span><span class='layout'>)</span>
<a name="line-64"></a>
<a name="line-65"></a> <span class='comment'>-- | edit the children of the root of a tree</span>
<a name="line-66"></a>
<a name="line-67"></a> <span class='varid'>changeChildren</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='layout'>(</span><span class='keyglyph'>[</span><span class='varid'>t</span> <span class='varid'>b</span><span class='keyglyph'>]</span> <span class='keyglyph'>-></span> <span class='keyglyph'>[</span><span class='varid'>t</span> <span class='varid'>b</span><span class='keyglyph'>]</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-68"></a> <span class='varid'>changeChildren</span> <span class='varid'>csf</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='layout'>(</span><span class='conid'>T</span><span class='varop'>.</span><span class='varid'>changeChildren</span> <span class='varid'>csf</span><span class='layout'>)</span>
<a name="line-69"></a>
<a name="line-70"></a> <span class='comment'>-- | edit the attribute of the root of a tree</span>
<a name="line-71"></a>
<a name="line-72"></a> <span class='varid'>changeNode</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='layout'>(</span><span class='varid'>b</span> <span class='keyglyph'>-></span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-73"></a> <span class='varid'>changeNode</span> <span class='varid'>nf</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='layout'>(</span><span class='conid'>T</span><span class='varop'>.</span><span class='varid'>changeNode</span> <span class='varid'>nf</span><span class='layout'>)</span>
<a name="line-74"></a>
<a name="line-75"></a> <span class='comment'>-- compound arrows</span>
<a name="line-76"></a>
<a name="line-77"></a> <span class='comment'>-- | apply an arrow element wise to all children of the root of a tree</span>
<a name="line-78"></a> <span class='comment'>-- collect these results and substitute the children with this result</span>
<a name="line-79"></a> <span class='comment'>--</span>
<a name="line-80"></a> <span class='comment'>-- example: @ processChildren isText @ deletes all subtrees, for which isText does not hold</span>
<a name="line-81"></a> <span class='comment'>--</span>
<a name="line-82"></a> <span class='comment'>-- example: @ processChildren (none \`when\` isCmt) @ removes all children, for which isCmt holds</span>
<a name="line-83"></a>
<a name="line-84"></a> <span class='varid'>processChildren</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-85"></a> <span class='varid'>processChildren</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>getNode</span>
<a name="line-86"></a> <span class='varop'>&&&</span>
<a name="line-87"></a> <span class='varid'>listA</span> <span class='layout'>(</span><span class='varid'>arrL</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>getChildren</span> <span class='varop'>>>></span> <span class='varid'>f</span><span class='layout'>)</span> <span class='comment'>-- new children, deterministic filter: single element result</span>
<a name="line-88"></a> <span class='varop'>>>></span>
<a name="line-89"></a> <span class='varid'>arr2</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>mkTree</span>
<a name="line-90"></a>
<a name="line-91"></a> <span class='comment'>-- | similar to processChildren, but the new children are computed by processing</span>
<a name="line-92"></a> <span class='comment'>-- the whole input tree</span>
<a name="line-93"></a> <span class='comment'>--</span>
<a name="line-94"></a> <span class='comment'>-- example: @ replaceChildren (deep isText) @ selects all subtrees for which isText holds</span>
<a name="line-95"></a> <span class='comment'>-- and substitutes the children component of the root node with this list</span>
<a name="line-96"></a>
<a name="line-97"></a> <span class='varid'>replaceChildren</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-98"></a> <span class='varid'>replaceChildren</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='varid'>arr</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>getNode</span>
<a name="line-99"></a> <span class='varop'>&&&</span>
<a name="line-100"></a> <span class='varid'>listA</span> <span class='varid'>f</span> <span class='comment'>-- compute new children</span>
<a name="line-101"></a> <span class='varop'>>>></span>
<a name="line-102"></a> <span class='varid'>arr2</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>mkTree</span>
<a name="line-103"></a>
<a name="line-104"></a> <span class='comment'>-- |</span>
<a name="line-105"></a> <span class='comment'>-- pronounced \"slash\", meaning g inside f</span>
<a name="line-106"></a> <span class='comment'>--</span>
<a name="line-107"></a> <span class='comment'>-- defined as @ f \/> g = f >>> getChildren >>> g @</span>
<a name="line-108"></a> <span class='comment'>--</span>
<a name="line-109"></a> <span class='comment'>-- example: @ hasName \"html\" \/> hasName \"body\" \/> hasName \"h1\" @</span>
<a name="line-110"></a> <span class='comment'>--</span>
<a name="line-111"></a> <span class='comment'>-- This expression selects</span>
<a name="line-112"></a> <span class='comment'>-- all \"h1\" elements in the \"body\" element of an \"html\" element, an expression, that</span>
<a name="line-113"></a> <span class='comment'>-- corresponds 1-1 to the XPath selection path \"html\/body\/h1\" </span>
<a name="line-114"></a>
<a name="line-115"></a> <span class='layout'>(</span><span class='varop'>/></span><span class='layout'>)</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-116"></a> <span class='varid'>f</span> <span class='varop'>/></span> <span class='varid'>g</span> <span class='keyglyph'>=</span> <span class='varid'>f</span> <span class='varop'>>>></span> <span class='varid'>getChildren</span> <span class='varop'>>>></span> <span class='varid'>g</span>
<a name="line-117"></a>
<a name="line-118"></a>
<a name="line-119"></a> <span class='comment'>-- |</span>
<a name="line-120"></a> <span class='comment'>-- pronounced \"outside\" meaning f containing g</span>
<a name="line-121"></a> <span class='comment'>--</span>
<a name="line-122"></a> <span class='comment'>-- defined as @ f \<\/ g = f \`containing\` (getChildren >>> g) @</span>
<a name="line-123"></a>
<a name="line-124"></a> <span class='layout'>(</span><span class='varop'></</span><span class='layout'>)</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-125"></a> <span class='varid'>f</span> <span class='varop'></</span> <span class='varid'>g</span> <span class='keyglyph'>=</span> <span class='varid'>f</span> <span class='varop'>`containing`</span> <span class='layout'>(</span><span class='varid'>getChildren</span> <span class='varop'>>>></span> <span class='varid'>g</span><span class='layout'>)</span>
<a name="line-126"></a>
<a name="line-127"></a>
<a name="line-128"></a> <span class='comment'>-- | recursively searches a whole tree for subtrees, for which a predicate holds.</span>
<a name="line-129"></a> <span class='comment'>-- The search is performed top down. When a tree is found, this becomes an element of the result</span>
<a name="line-130"></a> <span class='comment'>-- list. The tree found is not further examined for any subtress, for which the predicate also could hold.</span>
<a name="line-131"></a> <span class='comment'>-- See 'multi' for this kind of search.</span>
<a name="line-132"></a> <span class='comment'>--</span>
<a name="line-133"></a> <span class='comment'>-- example: @ deep isHtmlTable @ selects all top level table elements in a document</span>
<a name="line-134"></a> <span class='comment'>-- (with an appropriate definition for isHtmlTable) but no tables occuring within a table cell.</span>
<a name="line-135"></a>
<a name="line-136"></a> <span class='varid'>deep</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-137"></a> <span class='varid'>deep</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='varid'>f</span> <span class='comment'>-- success when applying f</span>
<a name="line-138"></a> <span class='varop'>`orElse`</span>
<a name="line-139"></a> <span class='layout'>(</span><span class='varid'>getChildren</span> <span class='varop'>>>></span> <span class='varid'>deep</span> <span class='varid'>f</span><span class='layout'>)</span> <span class='comment'>-- seach children</span>
<a name="line-140"></a>
<a name="line-141"></a>
<a name="line-142"></a> <span class='comment'>-- | recursively searches a whole tree for subrees, for which a predicate holds.</span>
<a name="line-143"></a> <span class='comment'>-- The search is performed bottom up.</span>
<a name="line-144"></a> <span class='comment'>--</span>
<a name="line-145"></a> <span class='comment'>-- example: @ deepest isHtmlTable @ selects all innermost table elements in a document</span>
<a name="line-146"></a> <span class='comment'>-- but no table elements containing tables. See 'deep' and 'multi' for other search strategies.</span>
<a name="line-147"></a>
<a name="line-148"></a> <span class='varid'>deepest</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-149"></a> <span class='varid'>deepest</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='layout'>(</span><span class='varid'>getChildren</span> <span class='varop'>>>></span> <span class='varid'>deepest</span> <span class='varid'>f</span><span class='layout'>)</span> <span class='comment'>-- seach children</span>
<a name="line-150"></a> <span class='varop'>`orElse`</span>
<a name="line-151"></a> <span class='varid'>f</span> <span class='comment'>-- no success: apply f to root</span>
<a name="line-152"></a>
<a name="line-153"></a>
<a name="line-154"></a> <span class='comment'>-- | recursively searches a whole tree for subtrees, for which a predicate holds.</span>
<a name="line-155"></a> <span class='comment'>-- The search is performed top down. All nodes of the tree are searched, even within the</span>
<a name="line-156"></a> <span class='comment'>-- subtrees of trees for which the predicate holds.</span>
<a name="line-157"></a> <span class='comment'>--</span>
<a name="line-158"></a> <span class='comment'>-- example: @ multy isHtmlTable @ selects all table elements, even nested ones.</span>
<a name="line-159"></a>
<a name="line-160"></a> <span class='varid'>multi</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='varid'>c</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='varid'>c</span>
<a name="line-161"></a> <span class='varid'>multi</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='varid'>f</span> <span class='comment'>-- combine result for root</span>
<a name="line-162"></a> <span class='varop'><+></span>
<a name="line-163"></a> <span class='layout'>(</span><span class='varid'>getChildren</span> <span class='varop'>>>></span> <span class='varid'>multi</span> <span class='varid'>f</span><span class='layout'>)</span> <span class='comment'>-- with result for all descendants</span>
<a name="line-164"></a>
<a name="line-165"></a> <span class='comment'>-- | recursively transforms a whole tree by applying an arrow to all subtrees,</span>
<a name="line-166"></a> <span class='comment'>-- this is done bottom up depth first, leaves first, root as last tree</span>
<a name="line-167"></a> <span class='comment'>--</span>
<a name="line-168"></a> <span class='comment'>-- example: @ processBottomUp (getChildren \`when\` isHtmlFont) @ removes all font tags in a HTML document, even nested ones</span>
<a name="line-169"></a> <span class='comment'>-- (with an appropriate definition of isHtmlFont)</span>
<a name="line-170"></a>
<a name="line-171"></a> <span class='varid'>processBottomUp</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-172"></a> <span class='varid'>processBottomUp</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='varid'>processChildren</span> <span class='layout'>(</span><span class='varid'>processBottomUp</span> <span class='varid'>f</span><span class='layout'>)</span> <span class='comment'>-- process all descendants first</span>
<a name="line-173"></a> <span class='varop'>>>></span>
<a name="line-174"></a> <span class='varid'>f</span> <span class='comment'>-- then process root</span>
<a name="line-175"></a>
<a name="line-176"></a> <span class='comment'>-- | similar to 'processBottomUp', but recursively transforms a whole tree by applying an arrow to all subtrees</span>
<a name="line-177"></a> <span class='comment'>-- with a top down depth first traversal strategie. In many cases 'processBottomUp' and 'processTopDown'</span>
<a name="line-178"></a> <span class='comment'>-- give same results.</span>
<a name="line-179"></a>
<a name="line-180"></a> <span class='varid'>processTopDown</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-181"></a> <span class='varid'>processTopDown</span> <span class='varid'>f</span> <span class='keyglyph'>=</span> <span class='varid'>f</span> <span class='comment'>-- first process root</span>
<a name="line-182"></a> <span class='varop'>>>></span>
<a name="line-183"></a> <span class='varid'>processChildren</span> <span class='layout'>(</span><span class='varid'>processTopDown</span> <span class='varid'>f</span><span class='layout'>)</span> <span class='comment'>-- then process all descendants of new root</span>
<a name="line-184"></a>
<a name="line-185"></a>
<a name="line-186"></a> <span class='comment'>-- | recursively transforms a whole tree by applying an arrow to all subtrees,</span>
<a name="line-187"></a> <span class='comment'>-- but transformation stops when a predicte does not hold for a subtree,</span>
<a name="line-188"></a> <span class='comment'>-- leaves are transformed first</span>
<a name="line-189"></a>
<a name="line-190"></a> <span class='varid'>processBottomUpWhenNot</span>
<a name="line-191"></a> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-192"></a> <span class='varid'>processBottomUpWhenNot</span> <span class='varid'>f</span> <span class='varid'>p</span>
<a name="line-193"></a> <span class='keyglyph'>=</span> <span class='layout'>(</span> <span class='varid'>processChildren</span> <span class='layout'>(</span><span class='varid'>processBottomUpWhenNot</span> <span class='varid'>f</span> <span class='varid'>p</span><span class='layout'>)</span>
<a name="line-194"></a> <span class='varop'>>>></span>
<a name="line-195"></a> <span class='varid'>f</span>
<a name="line-196"></a> <span class='layout'>)</span> <span class='varop'>`whenNot`</span> <span class='varid'>p</span>
<a name="line-197"></a>
<a name="line-198"></a> <span class='comment'>-- | recursively transforms a whole tree by applying an arrow to all subtrees,</span>
<a name="line-199"></a> <span class='comment'>-- but transformation stops when a tree is successfully transformed.</span>
<a name="line-200"></a> <span class='comment'>-- the transformation is done top down</span>
<a name="line-201"></a> <span class='comment'>--</span>
<a name="line-202"></a> <span class='comment'>-- example: @ processTopDownUntil (isHtmlTable \`guards\` tranformTable) @</span>
<a name="line-203"></a> <span class='comment'>-- transforms all top level table elements into something else, but inner tables remain unchanged</span>
<a name="line-204"></a>
<a name="line-205"></a> <span class='varid'>processTopDownUntil</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-206"></a> <span class='varid'>processTopDownUntil</span> <span class='varid'>f</span>
<a name="line-207"></a> <span class='keyglyph'>=</span> <span class='varid'>f</span>
<a name="line-208"></a> <span class='varop'>`orElse`</span>
<a name="line-209"></a> <span class='varid'>processChildren</span> <span class='layout'>(</span><span class='varid'>processTopDownUntil</span> <span class='varid'>f</span><span class='layout'>)</span>
<a name="line-210"></a>
<a name="line-211"></a> <span class='comment'>-- | computes a list of trees by applying an arrow to the input</span>
<a name="line-212"></a> <span class='comment'>-- and inserts this list in front of index i in the list of children</span>
<a name="line-213"></a> <span class='comment'>--</span>
<a name="line-214"></a> <span class='comment'>-- example: @ insertChildrenAt 0 (deep isCmt) @ selects all subtrees for which isCmt holds</span>
<a name="line-215"></a> <span class='comment'>-- and copies theses in front of the existing children</span>
<a name="line-216"></a>
<a name="line-217"></a> <span class='varid'>insertChildrenAt</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='conid'>Int</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-218"></a> <span class='varid'>insertChildrenAt</span> <span class='varid'>i</span> <span class='varid'>f</span>
<a name="line-219"></a> <span class='keyglyph'>=</span> <span class='varid'>listA</span> <span class='varid'>f</span> <span class='varop'>&&&</span> <span class='varid'>this</span> <span class='varop'>>>></span> <span class='varid'>arr2</span> <span class='varid'>insertAt</span>
<a name="line-220"></a> <span class='keyword'>where</span>
<a name="line-221"></a> <span class='varid'>insertAt</span> <span class='varid'>newcs</span>
<a name="line-222"></a> <span class='keyglyph'>=</span> <span class='conid'>T</span><span class='varop'>.</span><span class='varid'>changeChildren</span> <span class='layout'>(</span><span class='keyglyph'>\</span> <span class='varid'>cs</span> <span class='keyglyph'>-></span> <span class='keyword'>let</span>
<a name="line-223"></a> <span class='layout'>(</span><span class='varid'>cs1</span><span class='layout'>,</span> <span class='varid'>cs2</span><span class='layout'>)</span> <span class='keyglyph'>=</span> <span class='varid'>splitAt</span> <span class='varid'>i</span> <span class='varid'>cs</span>
<a name="line-224"></a> <span class='keyword'>in</span>
<a name="line-225"></a> <span class='varid'>cs1</span> <span class='varop'>++</span> <span class='varid'>newcs</span> <span class='varop'>++</span> <span class='varid'>cs2</span>
<a name="line-226"></a> <span class='layout'>)</span>
<a name="line-227"></a>
<a name="line-228"></a> <span class='comment'>-- | similar to 'insertChildrenAt', but the insertion position is searched with a predicate</span>
<a name="line-229"></a>
<a name="line-230"></a> <span class='varid'>insertChildrenAfter</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-231"></a> <span class='varid'>insertChildrenAfter</span> <span class='varid'>p</span> <span class='varid'>f</span>
<a name="line-232"></a> <span class='keyglyph'>=</span> <span class='varid'>replaceChildren</span>
<a name="line-233"></a> <span class='layout'>(</span> <span class='layout'>(</span> <span class='layout'>(</span> <span class='varid'>listA</span> <span class='varid'>getChildren</span>
<a name="line-234"></a> <span class='varop'>>>></span>
<a name="line-235"></a> <span class='varid'>spanA</span> <span class='varid'>p</span>
<a name="line-236"></a> <span class='layout'>)</span>
<a name="line-237"></a> <span class='varop'>&&&</span>
<a name="line-238"></a> <span class='varid'>listA</span> <span class='varid'>f</span>
<a name="line-239"></a> <span class='layout'>)</span>
<a name="line-240"></a> <span class='varop'>>>></span> <span class='varid'>arr2L</span> <span class='layout'>(</span><span class='keyglyph'>\</span> <span class='layout'>(</span><span class='varid'>xs1</span><span class='layout'>,</span> <span class='varid'>xs2</span><span class='layout'>)</span> <span class='varid'>xs</span> <span class='keyglyph'>-></span> <span class='varid'>xs1</span> <span class='varop'>++</span> <span class='varid'>xs</span> <span class='varop'>++</span> <span class='varid'>xs2</span><span class='layout'>)</span>
<a name="line-241"></a> <span class='layout'>)</span>
<a name="line-242"></a>
<a name="line-243"></a> <span class='comment'>-- | an arrow for inserting a whole subtree with some holes in it (a template)</span>
<a name="line-244"></a> <span class='comment'>-- into a document. The holes can be filled with contents from the input.</span>
<a name="line-245"></a> <span class='comment'>--</span>
<a name="line-246"></a> <span class='comment'>-- Example</span>
<a name="line-247"></a> <span class='comment'>--</span>
<a name="line-248"></a> <span class='comment'>-- > insertTreeTemplateTest :: ArrowXml a => a b XmlTree</span>
<a name="line-249"></a> <span class='comment'>-- > insertTreeTemplateTest</span>
<a name="line-250"></a> <span class='comment'>-- > = doc</span>
<a name="line-251"></a> <span class='comment'>-- > >>></span>
<a name="line-252"></a> <span class='comment'>-- > insertTemplate template pattern</span>
<a name="line-253"></a> <span class='comment'>-- > where</span>
<a name="line-254"></a> <span class='comment'>-- > doc -- the input data</span>
<a name="line-255"></a> <span class='comment'>-- > = constA "<x><y>The Title</y><z>The content</z></x>"</span>
<a name="line-256"></a> <span class='comment'>-- > >>> xread</span>
<a name="line-257"></a> <span class='comment'>-- > template -- the output template with 2 holes: xxx and yyy</span>
<a name="line-258"></a> <span class='comment'>-- > = constA "<html><head><title>xxx</title></head><body><h1>yyy</h1></body></html>"</span>
<a name="line-259"></a> <span class='comment'>-- > >>> xread</span>
<a name="line-260"></a> <span class='comment'>-- > pattern</span>
<a name="line-261"></a> <span class='comment'>-- > = [ hasText (== "xxx") -- fill the xxx hole with the input contents from element "x/y"</span>
<a name="line-262"></a> <span class='comment'>-- > :-> ( getChildren >>> hasName "y" >>> deep isText )</span>
<a name="line-263"></a> <span class='comment'>-- > </span>
<a name="line-264"></a> <span class='comment'>-- > , hasText (== "yyy") -- fill the yyy hole with the input contents from element "x/z"</span>
<a name="line-265"></a> <span class='comment'>-- > :-> ( getChildren >>> hasName "z" >>> getChildren )</span>
<a name="line-266"></a> <span class='comment'>-- > ]</span>
<a name="line-267"></a> <span class='comment'>--</span>
<a name="line-268"></a> <span class='comment'>-- computes the XML tree for the following document</span>
<a name="line-269"></a> <span class='comment'>--</span>
<a name="line-270"></a> <span class='comment'>-- > "<html><head><title>The Title</title></head><body><h1>The content</h1></body></html>"</span>
<a name="line-271"></a>
<a name="line-272"></a> <span class='varid'>insertTreeTemplate</span> <span class='keyglyph'>::</span> <span class='conid'>Tree</span> <span class='varid'>t</span> <span class='keyglyph'>=></span>
<a name="line-273"></a> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='keyglyph'>-></span> <span class='comment'>-- the the template</span>
<a name="line-274"></a> <span class='keyglyph'>[</span><span class='conid'>IfThen</span> <span class='layout'>(</span><span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='varid'>c</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span><span class='layout'>)</span><span class='keyglyph'>]</span> <span class='keyglyph'>-></span> <span class='comment'>-- the list of nodes in the template to be substituted</span>
<a name="line-275"></a> <span class='varid'>a</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span> <span class='layout'>(</span><span class='varid'>t</span> <span class='varid'>b</span><span class='layout'>)</span>
<a name="line-276"></a> <span class='varid'>insertTreeTemplate</span> <span class='varid'>template</span> <span class='varid'>choices</span>
<a name="line-277"></a> <span class='keyglyph'>=</span> <span class='varid'>insertTree</span> <span class='varop'>$<</span> <span class='varid'>this</span>
<a name="line-278"></a> <span class='keyword'>where</span>
<a name="line-279"></a> <span class='varid'>insertTree</span> <span class='varid'>t</span>
<a name="line-280"></a> <span class='keyglyph'>=</span> <span class='varid'>template</span> <span class='comment'>-- swap input and template</span>
<a name="line-281"></a> <span class='varop'>>>></span>
<a name="line-282"></a> <span class='varid'>processTemplate</span>
<a name="line-283"></a> <span class='keyword'>where</span>
<a name="line-284"></a> <span class='varid'>processTemplate</span>
<a name="line-285"></a> <span class='keyglyph'>=</span> <span class='varid'>choiceA</span> <span class='varid'>choices'</span> <span class='comment'>-- check whether node is a "hole" within the template</span>
<a name="line-286"></a> <span class='varop'>`orElse`</span>
<a name="line-287"></a> <span class='varid'>processChildren</span> <span class='varid'>processTemplate</span> <span class='comment'>-- else descent into template tree</span>
<a name="line-288"></a> <span class='varid'>choices'</span>
<a name="line-289"></a> <span class='keyglyph'>=</span> <span class='varid'>map</span> <span class='varid'>feedTree</span> <span class='varid'>choices</span> <span class='comment'>-- modify choices, such that the input is feed into the action arrows</span>
<a name="line-290"></a> <span class='varid'>feedTree</span> <span class='layout'>(</span><span class='varid'>cond</span> <span class='conop'>:-></span> <span class='varid'>action</span><span class='layout'>)</span>
<a name="line-291"></a> <span class='keyglyph'>=</span> <span class='varid'>cond</span> <span class='conop'>:-></span> <span class='layout'>(</span><span class='varid'>constA</span> <span class='varid'>t</span> <span class='varop'>>>></span> <span class='varid'>action</span><span class='layout'>)</span> <span class='comment'>-- the real input becomes the input at the holes</span>
</pre></body>
</html>