Generic list merge primitive: merges two sorted lists according to the Key and Order specifications, and unifies List3 with the result. The sort is stable, i.e. the order of elements with equal keys is preserved.
The Key argument determines which part of the list elements is considered the sorting key. If Key is 0, then the entire term is taken as the sorting key (in this case, the list can contain anything, including numbers, atoms, strings, compound terms, and even variables). If Key is a positive integer (or a list of those), then the list elements will get ordered by their Keyth subterm (in this case, the list must contain compound terms with appropriate subterms).
The Order argument specifies whether to use standard term order (@) or numeric order ($), whether the list is sorted into ascending (<, =<) or descending (>, >=) order, and whether duplicates are to be retained (=<, >=) or removed (<, >). The way to remember the Order argument is that it is the relation which holds between adjacent elements in the result.
Order ordering direction duplicates --------------------------------------------------------------- @< (or <) standard ascending removed @=< (or =<) standard ascending retained @> (or >) standard descending removed @>= (or >=) standard descending retained $< numeric ascending removed $=< numeric ascending retained $> numeric descending removed $>= numeric descending retainedThe alternative ordering criteria are:
Algorithm: For two lists [e1,e2,e3] and [f1,f2,f3], e1 is compared to f1. The resulting element (dictated by Key, Order and the standard ordering below, with ties being resolved in favour of the element from List1) is put into List3, and the process continued with the remaining input lists. This process continues until both lists are exhausted.
In particular, this will merge two sorted lists into a new sorted list, provided that the given ordering of the input lists is the same as the ordering parameters (Key,Order) of the merge. The merge is stable, i.e. the order of elements with equal keys is preserved. If List1 and List2 contain elements with identical keys, List1's elements will occur first in List3.
The other merging primitives may be defined in terms of merge/4 as follows:
merge(L1, L2, L3) :- merge(0, @=<, L1, L2, L3). number_merge(L1, L2, L3) :- merge(0, $=<, L1, L2, L3).
Success: merge(0,<,[2,4,6],[1,3,5],L). (gives L=[1,2,3,4,5,6]). merge(0,<,[f(1),f(7)],[f(8),f(10)],L). (gives L=[f(1),f(7),f(8),f(10)]). merge(0,<,[f(2),f(1)],[f(3),f(8)],L). (gives L=[f(2),f(1),f(3),f(8)]). merge(0,<,[f(2)],[f(6),f(1)],L). (gives L=[f(2),f(6),f(1)]). merge(0,>,[1,e,q],[Q,2,a],L). (gives Q=_g60,L=[_g60,1,2,a,e,q]). merge(0,>,[f(8),f(6)],[f(4),f(1)],L). (gives L=[f(8),f(6),f(4),f(1)]). merge(2,<,[f(2,1),f(6,4)],[f(6,3),f(8,6)],L). (gives L=[f(2,1),f(6,3),f(6,4),f(8,6)]). merge(2,<,[q(2,1),f(6,4)],[a(6,3),i(8,6)],L). (gives L=[q(2,1),a(6,3),f(6,4),i(8,6)]). merge(2,<,[f(a,b),f(c,a)],[f(k,a)],L). (gives L=[f(k,a),f(a,b),f(c,a)). merge(0,=<,[1,2],[3,4,4,5],L). (gives L=[1,2,3,4,4,5]). merge([2,1], =<, [f(1,a(1)), f(0,a(3))], [f(3,a(2)), f(1,a(4))], L). (gives L=[f(1,a(1)), f(3,a(2)), f(0,a(3)), f(1,a(4))]). Fail: merge(0,<,[2,4,6],[1,3,5],[1,2,3,4,5]). Error: merge(1,<,[f(1,2),f],[f(3,4),h(1,2)],L). (Error 5). merge(0.0,<,[f(1)],[f(2)],L). (Error 5). merge(2,<,[f(1,2)],[f(8)],L). (Error 6).