A common way to process sequences in XQuery (in addition to FLWOR expressions) is to iterate over them with recursive functions. The fn:sum()
function for example could be implemented as follows:
declare function fn:sum($seq as xs:anyAtomicType*) as xs:anyAtomicType { if(empty($seq)) then 0 else $seq[1] + fn:sum($seq[position() > 1]) };
The key idea is to walk over the sequence by repeatedly removing and processing the first element until the sequence is empty. The empty sequence is treated as a special case.
local:product($seq as xs:integer*) as xs:integer
that uses fn:fold-left
to calculate the product of all elements in the input sequence. Take care to choose the right value for the product of the empty sequence.local:min-max($seq as xs:double*) as xs:double*
that determines the minimum and maximum entry in a sequence of doubles in a single run.
local:min-max((-1,0,1))
returns (-1,1)
.A run is an already sorted sub-sequence of a potentially unsorted sequence. The integer sequence (4,5,6,9,1,10,0,8,2,0) for example consists of the runs (4,5,6,9), (1,10), (0,8), 2 and 0.
Write an XQuery function local:run-products($seq as xs:integer*) as xs:integer*
that takes a sequence of integers and returns the products of the elements in each run.
Examples:
local:run-products(())
returns ()
local:run-products((4,5,6,9,1,10,0,8,2,0))
returns (1080,10,0,2,0)
Hint:
Write a helper function that also keeps track of the product and the previous element of the run you are currently in and call it from local:run-products($seq)
.
In this exercise you will write your own sort algorithms in XQuery.
def qsort(list): if list == []: return [] else: pivot = list[0] lesser = qsort([x for x in list[1:] if x < pivot]) greater = qsort([x for x in list[1:] if x >= pivot]) return lesser + [pivot] + greater
Write a similar function local:quicksort($seq as xs:integer*) as xs:integer*
in XQuery that sorts a sequence of integers with the QuickSort algorithm.
local:merge($seq1 as xs:integer*, $seq2 as xs:integer*) as xs:integer*
that takes two already sorted sequences of integers as arguments and merges them into a single sorted sequence. Each sequence should only be traversed once.
Examples:
local:merge((1, 3, 4), (-1, 3, 42))
evaluates to (-1, 1, 3, 3, 4, 42)
local:merge((), (1, 2))
evaluates to (1, 2)
local:mergesort($seq as xs:integer*) as xs:integer*
using the function defined in the previous step that sorts a sequence of integers with the MergeSort algorithm.
Side note. Recurring lecture in summer terms: Declarative Programming
declare function local:product($seq as xs:integer*) as xs:integer { fn:fold-left($seq, 1, function($result, $i) { $result * $i }) }; declare function local:product-rec($seq as xs:integer*) as xs:integer { if(empty($seq)) then 1 else $seq[1] * local:product($seq[position() > 1]) }; declare function local:min-max($seq as xs:double*) as xs:double* { switch(count($seq)) case 0 return () case 1 return ($seq, $seq) default return let $h := $seq[1], $rec := local:min-max($seq[position() > 1]), $min := $rec[1], $max := $rec[2] return ( if($h lt $min) then $h else $min, if($h gt $max) then $h else $max ) }; declare function local:run-products($seq as xs:integer*) as xs:integer* { if(empty($seq)) then () else let $h := $seq[1] return local:run-products($h, $h, $seq[position() > 1]) }; declare function local:run-products( $prod as xs:integer, $curr as xs:integer, $seq as xs:integer* ) as xs:integer* { if(empty($seq)) then $prod else let $h := $seq[1], $t := $seq[position() > 1] return if($h ge $curr) then local:run-products($prod * $h, $h, $t) else ($prod, local:run-products($h, $h, $t)) }; declare function local:quicksort($seq as xs:integer*) as xs:integer* { if(empty($seq)) then () else let $pivot := $seq[1], $rest := $seq[position() > 1], $lesser := local:quicksort($rest[. lt $pivot]), $greater := local:quicksort($rest[. ge $pivot]) return ($lesser, $pivot, $greater) }; declare function local:merge($seq1 as xs:integer*, $seq2 as xs:integer*) as xs:integer* { if(empty($seq1)) then $seq2 else if(empty($seq2)) then $seq1 else let $a := $seq1[1], $b := $seq2[1] return if($a le $b) then ($a, local:merge($seq1[position() > 1], $seq2)) else ($b, local:merge($seq1, $seq2[position() > 1])) }; declare function local:mergesort($seq as xs:integer*) as xs:integer* { if(count($seq) lt 2) then $seq else let $mid := count($seq) idiv 2, $left := local:mergesort(subsequence($seq, 1, $mid)), $right := local:mergesort(subsequence($seq, $mid + 1)) return local:merge($left, $right) }; local:product(1 to 5) eq 120 and local:product-rec(1 to 5) eq 120 and deep-equal(local:min-max((-1,0,1)), (-1, 1)) and deep-equal(local:run-products((4,5,6,9,1,10,0,8,2,0)), (1080,10,0,2,0)) and deep-equal(local:quicksort((4,5,6,9,1,10,0,8,2,0)), (0, 0, 1, 2, 4, 5, 6, 8, 9, 10)) and deep-equal(local:mergesort((4,5,6,9,1,10,0,8,2,0)), (0, 0, 1, 2, 4, 5, 6, 8, 9, 10))