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.

1. Write a function 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.
2. Write a function 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.
   • Both values are returned as a sequence, so local:min-max((-1,0,1)) returns (-1,1).
   • If the input sequence is empty, the empty sequence should be returned.

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)
  (i.e., (4*5*6*9,1*10,0*8,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.

1. Consider this example of the QuickSort algorithm in Python:

   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.

2. Another efficient sorting algorithm is MergeSort. Write an XQuery implementation of it in the following steps:
   • Implement a function 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)

   • Write a function 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.