Recursion with XQuery with example
I have a database that looks like this (access it via $database
):
<country car_code="F" area="547030" capital="cty-france-paris">
<name>France</name>
<border country="AND" length="60"/>
<border country="E" length="623"/>
<border country="D" length="451"/>
<border country="I" length="488"/>
<border country="CH" length="573"/>
<border country="B" length="620"/>
<border country="L" length="73"/>
<border country="MC" length="4.4"/>
</country>
.....
other countries
I would like to write a function that gives the names of all countries reachable from France (or any other country) across land borders. First try (possibly with a lot of syntax errors and other errors, but the semantics of the program should be "clearer"):
declare function local:reachable($country as element())
as (return value should be a sequence of countries )
{
if $country == () (:if empty, it doesn't border to any other country:)
then ()
else(
$country/name UNION (for $bord in $country/border/@country return
local:reachable ($database/country/car_code = @bord ))
)
}
Calling this function:
local:reachable($database/country[@car_code = "F"])
Border countries in France must be:
<border country="AND" length="60"/>
<border country="E" length="623"/>
<border country="D" length="451"/>
<border country="I" length="488"/>
<border country="CH" length="573"/>
<border country="B" length="620"/>
<border country="L" length="73"/>
<border country="MC" length="4.4"/>
But we also need to find border countries for these countries. the end result must be "F", "AND", "E", "D", "I", "CH", "B", "L", "MC" ..., X, Y, Z, ( and other countries bordering these countries).
-
I know UNION is not defined, but is there anything else I can use? I just wanted to make it clearer what I want to do
-
One big problem other than syntax errors is that if "F" is bordering on "L" then "L" will border on "F", so my "function" will never finish - how can I access that?
-
Can I get some help with the syntax
-
If the question is not clear, please let me know so that I can clarify it further
source to share
Before we start
Here are some comments on your code:
$country as element()
defines a variable that MUST contain exactly one element, so it can never be empty; useelement()?
if the element is optional,element()*
if there can be any number of them, orelement()+
if there should be one or morethe sequence operator
,
can be used to construct sequences from other sequences:(1,2) , (3,4)
creates 2 sequences:(1,2)
and(3,4)
, then creates another one containing all the elements to others, resulting in:(1,2,3,4)
Let me change the element a bit countries
, so I'll remove the noise and make it a little easier for this demo. I also create a simple but complete map Let's say we have 2 neighboring countries U and K, and 4 others forming a square (each country is adjacent to 2 others): N, G, B and F. Any similarity to existing geography or politics only in your eyes :-)
<!--
Map: U K | N G
B F
-->
<countries>
<country id="U">
<name>Over the top</name>
<border idref="K"/>
</country>
<country id="K">
<name>Beyond the see</name>
<border idref="U"/>
</country>
<country id="N">
<name>Flatland</name>
<border idref="B"/>
<border idref="G"/>
</country>
<country id="G">
<name>Marxhome</name>
<border idref="N"/>
<border idref="F"/>
</country>
<country id="B">
<name>Beerium</name>
<border idref="N"/>
<border idref="F"/>
</country>
<country id="F">
<name>Grapeandcheese</name>
<border idref="B"/>
<border idref="G"/>
</country>
</countries>
Decision
The solution includes a recursive function that consumes a country queue for processing. Meanwhile, it accumulates a list of results one country at a time. The first country in the queue is required, add it to the result, then repeat to all neighboring countries that are not already in the queue, nor the current result. The augmented result is also transmitted.
xquery version "3.0";
declare variable $countries :=
<countries>
<!-- as above, just copy and paste it -->
</countries>;
declare function local:reachable(
$queue as element(country)*,
$result as element(country)*
) as element(country)*
{
if ( empty($queue) ) then (
(: we do not consider one country reachable from itself :)
tail($result)
)
else (
let $this := head($queue)
let $rest := tail($queue)
let $more := $this/border/@idref[not(. = ($queue, $result)/@id)]
return
local:reachable(
( $rest, $countries/country[@id = $more] ),
( $result, $this ))
)
};
(: for each countries, display its reachable countries
:)
for $c in $countries/country
order by $c/@id
let $r := local:reachable($c, ())
return
$c/name || ': ' || string-join($r/@id, ', ')
Result
Beerium: N, G, F
Grapeandcheese: N, G, B
Marxhome: N, B, F
Beyond the see: U
Flatland: G, B, F
Over the top: K
source to share