[xquery-talk] fn:sort: sort for strings in descending order

[Christian Grün]

Hi everyone,

As you may know, XQuery 3.1 introduces an interesting new fn:sort
function, which can be used as alternative for the order by clause in
FLWOR expressions [1]. It can e.g. be used to sort numbers in a
descending order:

sort(
1 to 10,
function($k) { -$k }
)

I would be interested if anyone has already tried to get the
descending order working for strings?

sort(
('A', 'AA', 'B'),
function($k) { ... }
)

I assume that string-to-codepoints could be used, and all Unicode
points could then be negated, and additionally longer Unicode
sequences would need to be preferred over shorter ones… But maybe
there is a more concise solution?

Thanks in advance,
Christian

[1] http://www.w3.org/TR/xpath-functions-31/#func-sort

_______________________________________________
***@x-query.com
http://x-query.com/mailman/li

[Rob Stapper]

Hi Christian,

I suppose it can't be this simple: reverse( sort( ('A', 'AA', 'B')))

Rob Stapper

-----Oorspronkelijk bericht-----
Van: talk-***@x-query.com [mailto:talk-***@x-query.com] Namens Christian Grün
Verzonden: donderdag 3 december 2015 12:49
Aan: ***@x-query.com
Onderwerp: [xquery-talk] fn:sort: sort for strings in descending order

Hi everyone,

As you may know, XQuery 3.1 introduces an interesting new fn:sort function, which can be used as alternative for the order by clause in FLWOR expressions [1]. It can e.g. be used to sort numbers in a descending order:

sort(
1 to 10,
function($k) { -$k }
)

I would be interested if anyone has already tried to get the descending order working for strings?

sort(
('A', 'AA', 'B'),
function($k) { ... }
)

I assume that string-to-codepoints could be used, and all Unicode points could then be negated, and additionally longer Unicode sequences would need to be preferred over shorter ones… But maybe there is a more concise solution?

Thanks in advance,
Christian

[1] http://www.w3.org/TR/xpath-functions-31/#func-sort

_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk


---
Dit e-mailbericht is gecontroleerd op virussen met Avast antivirussoftware.
http://www.avast.com


_______________________________________________
***@x-query.com
http://x-query.com/mailman/listin

[Michael Kay]

As Rob points out, the simplest solution for simple cases is to use reverse().

That doesn't work if you want a composite sort key - sort by ascending country then descending city. (Yes, an unconvincing use case, and frankly it's because of the difficulty of finding a convincing use case that we didn't include this capability).

If you know that the result of collation-key() will be xs:base64Binary then you can do it, I suspect, by

fn:sort($places, function($p) { $p!country, $p!city => collation-key() => bin:not() } )

where bin:not is from http://expath.org/spec/binary#not

Michael Kay
Saxonica

Post by Rob Stapper
Hi Christian,
I suppose it can't be this simple: reverse( sort( ('A', 'AA', 'B')))
Rob Stapper
-----Oorspronkelijk bericht-----
Verzonden: donderdag 3 december 2015 12:49
Onderwerp: [xquery-talk] fn:sort: sort for strings in descending order
Hi everyone,
sort(
1 to 10,
function($k) { -$k }
)
I would be interested if anyone has already tried to get the descending order working for strings?
sort(
('A', 'AA', 'B'),
function($k) { ... }
)
I assume that string-to-codepoints could be used, and all Unicode points could then be negated, and additionally longer Unicode sequences would need to be preferred over shorter ones… But maybe there is a more concise solution?
Thanks in advance,
Christian
[1] http://www.w3.org/TR/xpath-functions-31/#func-sort
_______________________________________________
http://x-query.com/mailman/listinfo/talk
---
Dit e-mailbericht is gecontroleerd op virussen met Avast antivirussoftware.
http://www.avast.com
_______________________________________________
http://x-query.com/mailman/listinfo/talk

_______________________________________________
***@x-query.com
http://x-

[Michael Kay]

Post by Michael Kay
As Rob points out, the simplest solution for simple cases is to use reverse().
That doesn't work if you want a composite sort key - sort by ascending country then descending city. (Yes, an unconvincing use case, and frankly it's because of the difficulty of finding a convincing use case that we didn't include this capability).
If you know that the result of collation-key() will be xs:base64Binary then you can do it, I suspect, by
fn:sort($places, function($p) { $p!country, $p!city => collation-key() => bin:not() } )
where bin:not is from http://expath.org/spec/binary#not

Sorry, that's wrong. The empty string sorts first in ascending order, under this function it will still sort first in descending order. Need to do something a bit more subtle.

Michael Kay
Saxonica



_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk

[Rob Stapper]

The difficulty in Christian's case lays in the variable string length. The
string length is part of ordering algorithm. For a reverse order one would
need to create a string with an inverse string length.
I would not know how to create a function nor how to define a collation that
does this.
I'm not sure if Michael's solution: returning an inverse binary image, how
intriguing that one may be, tackles this. (can't check this)
So, I would still put my money on the reverse()-method.

Rob

PS. The composite sort key is another tough cookie to crumble. I feel
challenged.

-----Oorspronkelijk bericht-----
Van: talk-***@x-query.com [mailto:talk-***@x-query.com] Namens
Michael Kay
Verzonden: donderdag 3 december 2015 15:19
Aan: Michael Kay
CC: ***@x-query.com; Christian Grün; Rob Stapper
Onderwerp: Re: [xquery-talk] fn:sort: sort for strings in descending order

Post by Michael Kay
As Rob points out, the simplest solution for simple cases is to use reverse().
That doesn't work if you want a composite sort key - sort by ascending

country then descending city. (Yes, an unconvincing use case, and frankly
it's because of the difficulty of finding a convincing use case that we
didn't include this capability).

Post by Michael Kay
If you know that the result of collation-key() will be xs:base64Binary

then you can do it, I suspect, by

Post by Michael Kay
fn:sort($places, function($p) { $p!country, $p!city => collation-key() => bin:not() } )
where bin:not is from http://expath.org/spec/binary#not

Sorry, that's wrong. The empty string sorts first in ascending order, under
this function it will still sort first in descending order. Need to do
something a bit more subtle.

Michael Kay
Saxonica



_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk


---
Dit e-mailbericht is gecontroleerd op virussen met Avast antivirussoftware.
http://www.avast.com


_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk

[Michael Kay]

Post by Rob Stapper
PS. The composite sort key is another tough cookie to crumble. I feel
challenged.

Because fn:sort produces a stable sort, one can always go back to the old punched-card technique of doing multiple sorts, in minor-to-major key order:

$places => sort(function($x){$x!city}) => reverse() => sort(function($x){$x!country})

Michael Kay
Saxonica



_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/talk

[Christian Grün]

Rob, Michael,

Thanks for your enlightening answers. The hint to fn:reverse was
helpful – I completely missed it – and I was not aware of the
punched-card technique (I overlooked that sort is stable).

One more use I case had in mind were top-k queries:

fn:sort(...)[position() = 1 to 5]

From the implementation point of view, such patterns can be sped up
with a min heap. I now realize that the heap can simply be replaced
with a max heap if an fn:sort call is wrapped by fn:reverse.

Christian
__________________________________

Post by Michael Kay

Post by Rob Stapper
PS. The composite sort key is another tough cookie to crumble. I feel
challenged.

$places => sort(function($x){$x!city}) => reverse() => sort(function($x){$x!country})
Michael Kay
Saxonica

_______________________________________________
***@x-query.com
http://x-query.com/mailman/listinfo/tal