Indeed, I believe that virtually

variables ≺ numbers ≺ atoms ≺ compound terms

It is subject to the following additional rules:

- Numbers are compared by value.
- All floating point numbers precede all integers.
- Atoms are compared alphabetically.
- Compound terms are first sorted by their arity, then alphabetically by their functor name, and finally recursively by their arguments, leftmost argument first.

?- a @< b.Yet thetrue.

?- a @< X.This violates properties we expect from pure predicates and prevents declarative debugging. Therefore, it is good practice to use dedicated comparison predicates with more declarative properties for specific domains. For example, in the case offalse.

`sort(Ls0, Ls)`is true iff the list`Ls`holds the elements of the list`Ls0`, sorted according to the standard order of terms.`Ls`contains*no duplicates*.`keysort(Pairs0, Pairs)`:`Pairs0`and`Pairs`are lists of`Key-Value`pairs. True iff`Pairs0`sorted by`Key`according to the standard order of terms is`Pairs`, where duplicates are*retained*, and the order of multiple elements with the same key is*also*retained. A sorting algorithm where the relative positions of equal elements are retained is called*stable*.

lists(["abcd", "abc", "abcde", "a", "ab"]).To solve this task, let us first define a relation between a single list and a pair of the form

list_pair(Ls, L-Ls) :- list_length(Ls, L).Using

?- lists(Lists), maplist(list_pair, Lists, Pairs0). Lists = ["abcd","abc","abcde","a","ab"],This representation makesPairs0 = [4-"abcd",3-"abc",5-"abcde",1-"a",2-"ab"].

?- lists(Lists), maplist(list_pair, Lists, Pairs0), keysort(Pairs0, Pairs). Lists = ["abcd","abc","abcde","a","ab"], Pairs0 = [4-"abcd",3-"abc",5-"abcde",1-"a",2-"ab"],Thus, to obtain a listPairs = [1-"a",2-"ab",3-"abc",4-"abcd",5-"abcde"].

In general, by constructing

Prolog implementations of the following sorting algorithms are available in

- bubble sort
- quicksort
- merge sort.

In particular, consider how naturally

quicksort([]) --> []. quicksort([L|Ls]) --> { partition(Ls, L, Smallers, Biggers) }, quicksort(Smallers), [L], quicksort(Biggers).This definition assumes the existence of

In general, it is often better to simply use the built-in predicates

Many Prolog programs

For example, suppose we want to

list_minimum([L|Ls], Min) :- foldl(minimum_, Ls, L, Min). minimum_(A, B, Min) :- Min #= min(A, B).This works in several directions:

?- list_minimum([3,1,2], M).Thus, when working on search tasks, do not get carried away with an imperative view. Instead, focus on a clear general description of all relations you want to define.M = 1.?- list_minimum([A,B], 0).clpz:(B in 0..sup), clpz:(0#=min(B,A)), clpz:(A in 0..sup).

In some cases, searching

k_n(N, Adjs) :- list_length(Nodes, N), Nodes ins 1..N, all_distinct(Nodes), once(label(Nodes)), maplist(adjs(Nodes), Nodes, Adjs). adjs(Nodes, Node, Node-As) :- tfilter(dif(Node), Nodes, As).In particular, we obtain for K

?- k_n(3, Adjs).As another example, KAdjs = [1-[2,3],2-[1,3],3-[1,2]] ; ... .

reachable(_, _, From, From). reachable(Adjs, Visited, From, To) :- maplist(dif(Next), Visited), member(From-As, Adjs), member(Next, As), reachable(Adjs, [From|Visited], Next, To).To compute the

?- k_n(3, Adjs), setof(To, reachable(Adjs, [], 1, To), Tos). Adjs = [1-[2,3],2-[1,3],3-[1,2]],The major drawback of this approach is that itTos = [1,2,3]; false.

?- list_length(_, N), portray_clause(N), k_n(N, Adjs), time(setof(To, reachable(Adjs, [], 1, To), Tos)), false. ... 6. % CPU time:This is because the number of0.171s7. % CPU time:1.454s8. % CPU time:13.628s9.

In this concrete case, we can solve the task in a much more efficient way. For example, we can use Warshall's algorithm for computing the transitive closure, with code similar to:

warshall(Adjs, Nodes0, Nodes) :- phrase(reachables(Nodes0, Adjs), Nodes1, Nodes0), sort(Nodes1, Nodes2), if_(Nodes2 = Nodes0, Nodes = Nodes2, warshall(Adjs, Nodes2, Nodes)). reachables([], _) --> []. reachables([Node|Nodes], Adjs) --> { member(Node-Rs, Adjs) }, Rs, reachables(Nodes, Adjs).Note how

?- k_n(9, Adjs), time(warshall(Adjs, [1], Tos)).This is clearly much more efficient. By implementing intelligent strategies, you can obtain elegant and efficient Prolog solutions for many search tasks.% CPU time: 0.000s..., Tos = [1,2,3,4,5,6,7,8,9] ; ... .

`Is0`contains no duplicates`Is`is a*permutation*of`Is0`- the elements of
`Is`are in*ascending*order.

ascending([]). ascending([I|Is]) :- foldl(ascending_, Is, I, _). ascending_(I, Prev, I) :- Prev #< I.For (2), we assume the availability of a predicate

Using these building blocks, we are ready to define

integers_ascending(Is0, Is) :- all_distinct(Is0), permutation(Is0, Is),This predicate implements a very naive sorting method calledascending(Is).

?- integers_ascending([3,1,2], Is).However, this method isIs = [1,2,3]; false.

?- time(integers_ascending([10,9,8,7,6,5,4,3,2,1], Ls)). % CPU time:We can10.109sLs = [1,2,3,4,5,6,7,8,9,10] ; ... .

integers_ascending(Is0, Is) :- all_distinct(Is0),With this simple change, we obtain:ascending(Is),permutation(Is0, Is).

?- time(integers_ascending([10,9,8,7,6,5,4,3,2,1], Ls)). % CPU time:By first stating the requirement that the list elements be in0.184sLs = [1,2,3,4,5,6,7,8,9,10] ; ... .

Note that even though combining search with early pruning can lead to tremendous performance improvements over generating all possibilities, dedicated algorithms that are carefully tailored to the task at hand are typically even more efficient. For example, in the concrete case of sorting a list of integers, you can simply use

?- sort([X,Y], [1,2]). X = 1, Y = 2.In contrast,

?- integers_ascending([X,Y], [1,2]). X = 1, Y = 2 ;X = 2, Y = 1; false.