Thanks! This works perfectly


On Feb 19, 2019, at 6:08 PM, Bridger Dyson-Smith <bdysonsmith@gmail.com> wrote:

Hi Michael -
that's a very nice solution! Thanks for sharing!

On Tue, Feb 19, 2019 at 6:14 AM Michael Seiferle <ms@basex.org> wrote:
Hi Guiseppe, 


unfortunately the example won’t be tail-call optimized as your last statement is not the function call itself but a sequence construction that happens to contain the function call.

Your function must be of the form:

f(x) => s(x)    if your termination condition is met (i.e. no more books)
f(x) => f(g(x))

Your function is defined (more or less) as something like:
f(x) => s(x)    if your termination condition is met (i.e. no more books)
f(x) =>  something  +  f(g(x))

So you have to get that something (i.e. the sequence concatenation) part inside your g-function, here’s what I think you might want:

Cross-posted as gist for better readability https://gist.github.com/micheee/ef75c9f30449c2de3406182ff2fdce50 
  declare variable $bookstore := <bookstore>{
    for $i in 1 to 300000
    return element book {
      element name {
        "Book " || $i
      },
      element price {
        1
      },
      element author {
        "Author "|| $i
      }
    }
  }
  </bookstore>;
  
  (:~ 
  Rolling total of prices
  @param $prices, accumulates the book prices.
         $prices[$n] contains the sum of prices for $book[position() <= $n]
  @param $books sequence of books not yet added to $prices
  :)
  declare function local:sum($prices, $books)
  {
      let $book   := head($books)           (: Get first book in sequence :)
      let $prices := if(count($prices) = 0) (: if empty, initialize prices with first price :)
        then ($book/price )       
        else (                    (: add the current rolling total to the list of rolling totals :)
                                  (: that’s the concatenation part :)
          $prices,
          element price { $prices[count($prices)] + $book/price } 
        )  
      return (
        if(count($books) > 1) then 
          local:sum($prices, tail($books))  (: here's the tail call :)
        else $prices
      )
  };
  
  <prices>
  {
      local:sum((), $bookstore/book) 
  }
  </prices>

You can check if your query is tail-call optimized using the query info panel: 
- mark as tail call: local:sum(if(empty($prices_2)) then (hea...


Hope this helps!

Best from Konstanz

Michael

Am 18.02.2019 um 19:12 schrieb Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de>:

Hi Jonathan, 

Thanks for that. However, it returns the same stack overflow error as the other script, when <book/> are 38000.  Encreasing the JVM size does not help either.

On Feb 18, 2019, at 4:51 PM, Jonathan Robie <jonathan.robie@gmail.com> wrote:

To make it tail-recursive, make the recursive call the last operation in the function.


The else() clause is what keeps it from being tail recursive.  Something like this should work:

declare variable $bookstore := <bookstore>
  <book>
    <name>story</name>
    <price>50.00</price>
    <author>smith</author>
  </book>
  <book>
    <name>history</name>
    <price>150.00</price>
    <author>kelly</author>
  </book>
  <book>
    <name>epic</name>
    <price>300.00</price>
    <author>jones</author>
  </book>
</bookstore>;

declare function local:sum($books, $sum)
{
    let $sum :=  $sum + $books[1]/price
    return (
        <price>{ $sum }</price>,
        $books[2] ! local:sum(tail($books), $sum)
    )
};

<prices>
{
    local:sum($bookstore/book, 0)
}
</prices>


Jonathan

On Mon, Feb 18, 2019 at 10:24 AM Giuseppe G. A. Celano <celano@informatik.uni-leipzig.de> wrote:
I am writing a recursive function which is similar to the one here:

https://stackoverflow.com/questions/27702718/to-add-values-in-cumulative-format

Interestingly, local:sum() works if there are not many <book/>. However with 38000 book element I get the error "Stack Overflow: Try tail recursion".

Any idea?

Ciao,
Giuseppe