sorting a list

[giacomociti]

hello, I would like to sort a list.

I could almost do it like this:

@prefix list: <http://www.w3.org/2000/10/swap/list#> .
@prefix math: <http://www.w3.org/2000/10/swap/math#> .
@prefix : <hrttp://ex.org/> .

{ (3 5 8 3 4) :sorted ?result} => { :result :is ?result } .

() :sorted () .

{
  ?list :sorted ?sorted 
}
<=
{
    ?list math:min ?min .
    (?list ?min) list:remove ?rest .
    ?rest :sorted ?sortedRest .
    ?sorted list:firstRest (?min ?sortedRest) .
} 
.

except for the duplicates and the fact that it works only backwards (why?).
Is there a better way, or maybe some built-in which I am missing?

Thanks

[josd]

There is a built-in list:sort in eye but it removes duplicates.
If you don't want the remove duplicates, here is a possible implementation

@prefix list: <http://www.w3.org/2000/10/swap/list#> .
@prefix math: <http://www.w3.org/2000/10/swap/math#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .
@prefix : <hrttp://ex.org/> .

{ (3 5 8 3 4) :sort ?result} => { :result :is ?result } .

# sort
() :sort () .

{ ?a :sort ?b } <= {
    ?a list:firstRest (?c ?d) .
    (?c ?d) :split (?e ?f) .
    ?e :sort ?g .
    ?f :sort ?h .
    ?i list:firstRest (?c ?h) .
    (?g ?i) list:append ?b .
} .

# split
(?x ()) :split (() ()) .

{ (?a ?b) :split (?c ?d) } <= {
    ?b list:firstRest (?e ?f) .
    (
        {
            ?a math:notLessThan ?e .
        }
        {
            ?c list:firstRest (?e ?g) .
            ?d log:equalTo ?h .
        }
        {
            ?c log:equalTo ?g .
            ?d list:firstRest (?e ?h) .
        }
    ) log:ifThenElseIn ?scope .
    (?a ?f) :split (?g ?h) .
} .

which gives

:result :is (3 3 4 5 8).

[giacomociti]

I think the built-in is fine in most use cases (I didn't notice it because I was looking only at examples), but your 'duplicate-aware' solution is also interesting, thanks.
Btw, it also relies on backward rules and I would like to learn a bit more about why they are necessary in these examples.
Can you point me to some (not too technical) explanation?

[josd]

Btw, it also relies on backward rules and I would like to learn a bit more about why they are necessary in these examples.
Can you point me to some (not too technical) explanation?

The general motivation for backward rules is given by TimBL in https://www.w3.org/2000/10/swap/doc/tutorial-1.pdf page 20

Tip: Its useful to think of where the rule engine is going to start with some data, which will alow it to find the
values of variables.
{ ?x math:greaterThan ?y. } => { ?x :moreInterestingThan ?y }.
This doesn’t give cwm, a forward reasoner, much to go on. It won’t list all pairs of number where the first is
greater than the second. A backward reasoner, such as Euler, will be able to use that. Future semantic web
engines will get smarter about picking rules to use and algorithms to use them with.

Euler is now eye but it needs a hint to know when to do backward chaining and this is when it sees a <= in the rule, so in the
above example you should write { ?x :moreInterestingThan ?y } <= { ?x math:greaterThan ?y. }.
Such rules are basically running "just-in-time" that is "the conclusion is true if the premis is true".