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([[a,b,c,d], [a,b,c], [a,b,c,d,e], [a], [a,b]]).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 = [[a, b, c, d], [a, b, c], [a, b, c, d, e], [a], [a, b]],This representation makesPairs0 = [4-[a, b, c, d], 3-[a, b, c], 5-[a, b, c, d, e], 1-[a], 2-[a, b]].

?- lists(Lists), maplist(list_pair, Lists, Pairs0), keysort(Pairs0, Pairs). Lists = [[a, b, c, d], [a, b, c], [a, b, c, d, e], [a], [a, b]], Pairs0 = [4-[a, b, c, d], 3-[a, b, c], 5-[a, b, c, d, e], 1-[a], 2-[a, b]],Thus, to obtain a listPairs = [1-[a], 2-[a, b], 3-[a, b, c], 4-[a, b, c, d], 5-[a, b, c, d, e]].

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).A in 0..sup, 0#=min(B, A), B 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] .

?- list_length(_, N), portray_clause(N), k_n(N, Adjs), time(setof(To, reachable(Adjs, [], 1, To), Tos)), false. ... 6. % 110,079 inferences, 0.012 CPU inThis is because the number of0.012 seconds(98% CPU, 9334266 Lips) 7. % 914,953 inferences, 0.093 CPU in0.098 seconds(95% CPU, 9816460 Lips) 8. % 8,446,107 inferences, 0.823 CPU in0.837 seconds(98% CPU, 10265329 Lips) 9. % 85,982,043 inferences, 8.086 CPU in8.135 seconds(99% CPU, 10633230 Lips)

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)). % 322 inferences, 0.000 CPU inThis is clearly much more efficient. By implementing intelligent strategies, you can obtain elegant and efficient Prolog solutions for many search tasks.0.000 seconds(93% CPU, 4735294 Lips) ... 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)). % 64,398,640 inferences, 9.928 CPU inWe can9.994 seconds(99% CPU, 6486524 Lips) Ls = [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)). % 168,432 inferences, 0.025 CPU inBy first stating the requirement that the list elements be in0.026 seconds(98% CPU, 6699761 Lips) Ls = [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.