[xquery-talk] Fold-right

[Michael Kay]

> On 12 Jan 2017, at 12:21, W.S. Hager <wshager at gmail.com> wrote:
> 
> Hello,
> 
> Not sure if anyone already noticed, but there's an error in the XPath/XQuery F&O docs, where the example implementation of array:fold will always return an array...

If they have noticed, they haven't reported it. Logged here as a bug:

https://www.w3.org/Bugs/Public/show_bug.cgi?id=30045

If you spot such things in future, please report them using the feedback mechanisms described in the status section of the spec.
> 
> More importantly,

No, I think the subsequent points are far less important. The code used to specify the effect of the function is intended to be a specification, not an efficient implementation.

> it seems to me that a textbook implementation of fold-right was used, without the notice that this will only work in a lazy evaluation context. If you inspect the code as eagerly evaluated, you'll see that the array is looped over multiple times (the result is the same of course). This makes for a very inefficient loop AFAICT, but I may be mistaken.

I don't think it's true that it only works with lazy evaluation. It may well be true that it only works efficiently with lazy evaluation, but that's irrelevant: this is a specfication of the effect of the function, not a proposed implementation.
> 
> 
> Is there any assumption about the laziness of an XQuery implementation? Are there any a priori lazy implementations out there?
> 

I think an implementation without lazy evaluation would be incredibly inefficient, and I would expect that most serious implementations use lazy evaluation to a lesser or greater extent. Certainly Saxon does so. I have seen open source XPath implementations that materialize all intermediate results, and frankly I don't think such an implementation is fit for purpose.

As it happens, this very morning I've been working on a problem where excessive use of lazy evaluation causes stack overflow problems when fold-left is used to process a very long sequence: you can find it here if you're interested:

https://saxonica.plan.io/issues/3106

Michael Kay
Saxonica