[xquery-talk] Implementing algorithms involving state across iterations in XQuery

[Charles Duffy]

Howdy --

I'd like to implement an algorithm akin to that described by the following
pseudocode in XQuery 3 (my implementation of choice is BaseX):

declare variable $inputs external;

declare function local:map-contains-prefix-of($map, $element) {
for $map-key in map:keys($map)
where fn:string-prefix($map-key, $element/key)
return map:get($map, $map-key)
}

declare function local:result-collection($inputs) {
let $already-seen := map:new() (: intended to be "updated" / shadowed
later :)
for $element in $inputs
where not(local:map-contains-prefix-of($already-seen, $element))
let $result := expensive-operation($element)
let $already-seen := map:new(($already-seen,
map:entry(get-key($element), $result))
return $already-seen
}

local:result-collections($inputs)[last()]

...to explain in prose:

- I have a sequence of inputs, and expect to generate a shorter sequence
of outputs.
- I have a call, expensive-operation(), which results in (1) the desired
return value for a given input, and (2) information necessary and
sufficient to identify which other input elements will have the same output
relatively cheaply (in this example, done with a string comparison).
- I'm trying to determine how to minimize the number of calls to
expensive-operation() in an XQuery statement while still generating the
desired output.

While I know how to do this in a few other functional languages (for
instance, in Clojure with its atoms), I'm a bit lost in XQuery. Could I ask
for a bit of clue?

Thanks!

[Leonard Wörteler]

Charles,

Post by Charles Duffy
While I know how to do this in a few other functional languages (for
instance, in Clojure with its atoms), I'm a bit lost in XQuery. Could I
ask for a bit of clue?

I think you are looking for `fn:fold-left(...)` and/or
`fn:fold-right(...)` [1]. They can be used to thread some kind of state
through while iterating over a sequence. `fn:fold-left($seq, $z, $f)`

Post by Charles Duffy
$accum <- $z;
foreach($item in $seq) {
$accum <- $f($accum, $item);
}
return $accum;
fn:fold-left(
$inputs,
map:new(),
function($already-seen, $element) {
if(local:map-contains-prefix-of($already-seen, $element))
then $already-seen
else (
let $result := expensive-operation($element)
return map:new((
$already-seen,
map:entry(get-key($element), $result)
))
)
}
)

Hope that helps,
Leo

[1] http://www.w3.org/TR/xpath-functions-30/#func-fold-left