Prolog - 列表

---

在本章中，我们将讨论 Prolog 中的重要概念之一：列表。它是一种可在不SymPy况下用于非数字编程的数据结构。列表用于将Atomics存储为集合。

在后续部分中，我们将讨论以下主题 -

• Prolog 中列表的表示

• Prolog 的基本操作，例如插入、删除、更新、追加。

• 重新定位运算符，例如排列、组合等。

• 集合运算如集合并集、集合交集等。

列表的表示

列表是一种简单的数据结构，广泛应用于非数值编程中。列表由任意数量的项目组成，例如红色、绿色、蓝色、白色、黑色。它将表示为[红、绿、蓝、白、暗]。元素列表将用方括号括起来。

列表可以为空或非空。在第一种情况下，列表简单地写为 Prolog Atomics []。在第二种情况下，列表由以下两部分组成 -

• 第一项，称为列表的头部；

• 列表的剩余部分称为tail。

假设我们有一个类似的列表：[红，绿，蓝，白，暗]。这里头部是红色的，尾巴是[绿色，蓝色，白色，深色]。所以尾部是另一个列表。

现在，让我们考虑有一个列表，L = [a, b, c]。如果我们写 Tail = [b, c] 那么我们也可以将列表 L 写为 L = [ a | 尾巴]。这里，竖线（|）将头部和尾部分开。

因此以下列表表示也是有效的 -

• [a，b，c] = [x | [b、c]]

• [a，b，c] = [a，b | [C] ]

• [a，b，c] = [a，b，c | [ ] ]

对于这些属性，我们可以将列表定义为 -

一种数据结构，要么是空的，要么由两部分组成——头和尾。尾部本身必须是一个列表。

列表的基本操作

下表包含序言列表上的各种操作 -

会员运营

在这个操作中，我们可以检查成员X是否存在于列表L中？那么如何检查这一点呢？好吧，我们必须定义一个谓词才能做到这一点。假设谓词名称为list_member(X,L)。该谓词的目标是检查 X 是否存在于 L 中。

为了设计这个谓词，我们可以遵循这些观察结果。X 是 L 的成员，如果 -

• X 是 L 的头部，或者

• X是L尾部的成员

程序

list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

输出

| ?- [list_basics].
compiling D:/TP Prolog/Sample_Codes/list_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/list_basics.pl compiled, 1 lines read - 467 bytes written, 13 ms

yes
| ?- list_member(b,[a,b,c]).

true ?

yes
| ?- list_member(b,[a,[b,c]]).

no
| ?- list_member([b,c],[a,[b,c]]).

true ?

yes
| ?- list_member(d,[a,b,c]).

no
| ?- list_member(d,[a,b,c]).

长度计算

这用于查找列表 L 的长度。我们将定义一个谓词来完成此任务。假设谓词名称为list_length(L,N)。这将 L 和 N 作为输入参数。这将对列表 L 中的元素进行计数，并将 N 实例化为其数量。与我们之前涉及列表的关系的情况一样，考虑两种情况是有用的 -

• 如果列表为空，则长度为 0。

• 如果链表不为空，那么L = [Head|Tail]，那么它的长度就是1+Tail的长度。

程序

list_length([],0).
list_length([_|TAIL],N) :- list_length(TAIL,N1), N is N1 + 1.

输出

| ?- [list_basics].
compiling D:/TP Prolog/Sample_Codes/list_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/list_basics.pl compiled, 4 lines read - 985 bytes written, 23 ms

yes
| ?- list_length([a,b,c,d,e,f,g,h,i,j],Len).

Len = 10

yes
| ?- list_length([],Len).

Len = 0

yes
| ?- list_length([[a,b],[c,d],[e,f]],Len).

Len = 3

yes
| ?-

级联

两个列表的串联意味着将第二个列表的列表项添加到第一个列表之后。因此，如果两个列表是 [a,b,c] 和 [1,2]，那么最终列表将是 [a,b,c,1,2]。因此，为了完成此任务，我们将创建一个名为 list_concat() 的谓词，它将采用第一个列表 L1、第二个列表 L2 和 L3 作为结果列表。这里有两个观察结果。

• 如果第一个列表为空，第二个列表为 L，则结果列表将为 L。

• 如果第一个列表不为空，则将其写为[Head|Tail]，将Tail与L2递归连接，并以[Head|New List]的形式存储到新列表中。

程序

list_concat([],L,L).
list_concat([X1|L1],L2,[X1|L3]) :- list_concat(L1,L2,L3).

输出

| ?- [list_basics].
compiling D:/TP Prolog/Sample_Codes/list_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/list_basics.pl compiled, 7 lines read - 1367 bytes written, 19 ms

yes
| ?- list_concat([1,2],[a,b,c],NewList).

NewList = [1,2,a,b,c]

yes
| ?- list_concat([],[a,b,c],NewList).

NewList = [a,b,c]

yes
| ?- list_concat([[1,2,3],[p,q,r]],[a,b,c],NewList).

NewList = [[1,2,3],[p,q,r],a,b,c]

yes
| ?-

从列表中删除

假设我们有一个列表 L 和一个元素 X，我们必须从 L 中删除 X。所以有三种情况 -

• 如果X是唯一的元素，那么删除它后，它将返回空列表。

• 如果X是L的头部，则结果列表将是尾部部分。

• 如果 X 存在于 Tail 部分，则从那里递归删除。

程序

list_delete(X, [X], []).
list_delete(X,[X|L1], L1).
list_delete(X, [Y|L2], [Y|L1]) :- list_delete(X,L2,L1).

输出

| ?- [list_basics].
compiling D:/TP Prolog/Sample_Codes/list_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/list_basics.pl compiled, 11 lines read - 1923 bytes written, 25 ms

yes
| ?- list_delete(a,[a,e,i,o,u],NewList).

NewList = [e,i,o,u] ?

yes
| ?- list_delete(a,[a],NewList).

NewList = [] ?

yes
| ?- list_delete(X,[a,e,i,o,u],[a,e,o,u]).

X = i ? ;

no
| ?-

追加到列表中

附加两个列表意味着将两个列表添加在一起，或将一个列表添加为一项。现在，如果该项目存在于列表中，则追加功能将不起作用。因此，我们将创建一个谓词，即 list_append(L1, L2, L3)。以下是一些观察结果 -

• 设A是一个元素，L1是一个列表，当L1已经有A时，输出也将是L1。

• 否则新列表将为 L2 = [A|L1]。

程序

list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_append(A,T,T) :- list_member(A,T),!.
list_append(A,T,[A|T]).

在本例中，我们使用了 (!) 符号，即所谓的剪切。所以当第一行执行成功后，我们就把它剪掉，这样就不会执行接下来的操作了。

输出

| ?- [list_basics].
compiling D:/TP Prolog/Sample_Codes/list_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/list_basics.pl compiled, 14 lines read - 2334 bytes written, 25 ms

(16 ms) yes
| ?- list_append(a,[e,i,o,u],NewList).

NewList = [a,e,i,o,u]

yes
| ?- list_append(e,[e,i,o,u],NewList).

NewList = [e,i,o,u]

yes
| ?- list_append([a,b],[e,i,o,u],NewList).

NewList = [[a,b],e,i,o,u]

yes
| ?-

插入列表

此方法用于将项目 X 插入列表 L 中，结果列表将是 R。因此谓词将采用这种形式 list_insert(X, L, R)。所以这可以将X插入L中所有可能的位置。如果我们看得更近，就会有一些观察结果。

• 如果我们执行list_insert(X,L,R)，我们可以使用list_delete(X,R,L)，因此从R中删除X并创建新列表L。

程序

list_delete(X, [X], []).
list_delete(X,[X|L1], L1).
list_delete(X, [Y|L2], [Y|L1]) :- list_delete(X,L2,L1).

list_insert(X,L,R) :- list_delete(X,R,L).

输出

| ?- [list_basics].
compiling D:/TP Prolog/Sample_Codes/list_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/list_basics.pl compiled, 16 lines read - 2558 bytes written, 22 ms

(16 ms) yes
| ?- list_insert(a,[e,i,o,u],NewList).

NewList = [a,e,i,o,u] ? a

NewList = [e,a,i,o,u]

NewList = [e,i,a,o,u]

NewList = [e,i,o,a,u]

NewList = [e,i,o,u,a]

NewList = [e,i,o,u,a]

(15 ms) no
| ?-

列表项的重新定位操作

以下是重新定位操作 -

排列运算

此操作将更改列表项位置并生成所有可能的结果。所以我们将创建一个谓词list_perm(L1,L2)，这将生成L1的所有排列，并将它们存储到L2中。为此，我们需要 list_delete() 子句来提供帮助。

为了设计这个谓词，我们可以遵循下面给出的一些观察结果 -

X 是 L 的成员，如果 -

• 如果第一个列表为空，则第二个列表也必须为空。

• 如果第一个列表不为空，则其形式为 [X | L]，这样一个列表的排列可以构造为，首先对L进行排列得到L1，然后将X在任意位置插入到L1中。

程序

list_delete(X,[X|L1], L1).
list_delete(X, [Y|L2], [Y|L1]) :- list_delete(X,L2,L1).

list_perm([],[]).
list_perm(L,[X|P]) :- list_delete(X,L,L1),list_perm(L1,P).

输出

| ?- [list_repos].
compiling D:/TP Prolog/Sample_Codes/list_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/list_repos.pl compiled, 4 lines read - 1060 bytes written, 17 ms

(15 ms) yes
| ?- list_perm([a,b,c,d],X).

X = [a,b,c,d] ? a

X = [a,b,d,c]

X = [a,c,b,d]

X = [a,c,d,b]

X = [a,d,b,c]

X = [a,d,c,b]

X = [b,a,c,d]

X = [b,a,d,c]

X = [b,c,a,d]

X = [b,c,d,a]

X = [b,d,a,c]

X = [b,d,c,a]

X = [c,a,b,d]

X = [c,a,d,b]

X = [c,b,a,d]

X = [c,b,d,a]

X = [c,d,a,b]

X = [c,d,b,a]

X = [d,a,b,c]

X = [d,a,c,b]

X = [d,b,a,c]

X = [d,b,c,a]

X = [d,c,a,b]

X = [d,c,b,a]

(31 ms) no
| ?-

反向操作

假设我们有一个列表 L = [a,b,c,d,e]，并且我们想要反转元素，因此输出将是 [e,d,c,b,a]。为此，我们将创建一个子句 list_reverse(List, ReversedList)。以下是一些观察结果 -

• 如果列表为空，则结果列表也将为空。

• 否则放置列表项，即[Head|Tail]，并递归地反转Tail项，并与Head连接。

• 否则放置列表项，即[Head|Tail]，并递归地反转Tail项，并与Head连接。

程序

list_concat([],L,L).
list_concat([X1|L1],L2,[X1|L3]) :- list_concat(L1,L2,L3).

list_rev([],[]).
list_rev([Head|Tail],Reversed) :-
   list_rev(Tail, RevTail),list_concat(RevTail, [Head],Reversed).

输出

| ?- [list_repos].
compiling D:/TP Prolog/Sample_Codes/list_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/list_repos.pl compiled, 10 lines read - 1977 bytes written, 19 ms

yes
| ?- list_rev([a,b,c,d,e],NewList).

NewList = [e,d,c,b,a]

yes
| ?- list_rev([a,b,c,d,e],[e,d,c,b,a]).

yes
| ?-

移位操作

使用 Shift 操作，我们可以将列表中的一个元素旋转地向左移动。因此，如果列表项是[a,b,c,d]，那么移位后，它将是[b,c,d,a]。所以我们将创建一个子句list_shift(L1, L2)。

• 我们将列表表示为[Head|Tail]，然后递归地将Head和Tail连接起来，这样我们就能感觉到元素发生了移位。

• 这也可以用来检查两个列表是否移动到一个位置。

程序

list_concat([],L,L).
list_concat([X1|L1],L2,[X1|L3]) :- list_concat(L1,L2,L3).

list_shift([Head|Tail],Shifted) :- list_concat(Tail, [Head],Shifted).

输出

| ?- [list_repos].
compiling D:/TP Prolog/Sample_Codes/list_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/list_repos.pl compiled, 12 lines read - 2287 bytes written, 10 ms

yes
| ?- list_shift([a,b,c,d,e],L2).

L2 = [b,c,d,e,a]

(16 ms) yes
| ?- list_shift([a,b,c,d,e],[b,c,d,e,a]).

yes
| ?-

订单操作

这里我们将定义一个谓词 list_order(L) 来检查 L 是否有序。因此，如果 L = [1,2,3,4,5,6]，则结果将为 true。

• 如果只有一个元素，则该元素已排序。

• 否则，将前两个元素 X 和 Y 作为 Head，其余作为 Tail。如果 X =< Y，则使用参数 [Y|Tail] 再次调用该子句，因此将从下一个元素开始递归检查。

程序

list_order([X, Y | Tail]) :- X =< Y, list_order([Y|Tail]).
list_order([X]).

输出

| ?- [list_repos].
compiling D:/TP Prolog/Sample_Codes/list_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/list_repos.pl:15: warning: singleton variables [X] for list_order/1
D:/TP Prolog/Sample_Codes/list_repos.pl compiled, 15 lines read - 2805 bytes written, 18 ms

yes
| ?- list_order([1,2,3,4,5,6,6,7,7,8]).

true ?

yes
| ?- list_order([1,4,2,3,6,5]).

no
| ?-

对列表进行设置操作

我们将尝试编写一个子句来获取给定集合的所有可能子集。因此，如果集合是 [a,b]，那么结果将是 [], [a], [b], [a,b]。为此，我们将创建一个子句 list_subset(L, X)。它将采用 L 并将每个子集返回到 X 中。因此我们将按以下方式进行 -

• 如果列表为空，则子集也为空。

• 通过保留 Head 递归地找到子集，并且

• 进行另一个递归调用，我们将删除 Head。

程序

list_subset([],[]).
list_subset([Head|Tail],[Head|Subset]) :- list_subset(Tail,Subset).
list_subset([Head|Tail],Subset) :- list_subset(Tail,Subset).

输出

| ?- [list_set].
compiling D:/TP Prolog/Sample_Codes/list_set.pl for byte code...
D:/TP Prolog/Sample_Codes/list_set.pl:3: warning: singleton variables [Head] for list_subset/2
D:/TP Prolog/Sample_Codes/list_set.pl compiled, 2 lines read - 653 bytes written, 7 ms

yes
| ?- list_subset([a,b],X).

X = [a,b] ? ;

X = [a] ? ;

X = [b] ? ;

X = []

(15 ms) yes
| ?- list_subset([x,y,z],X).

X = [x,y,z] ? a

X = [x,y]

X = [x,z]

X = [x]

X = [y,z]

X = [y]

X = [z]

X = []

yes
| ?-

联盟运作

让我们定义一个名为 list_union(L1,L2,L3) 的子句，因此这将获取 L1 和 L2，并对它们执行 Union，并将结果存储到 L3 中。如您所知，如果两个列表两次具有相同的元素，那么合并后将只有一个。所以我们需要另一个辅助子句来检查成员资格。

程序

list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_union([X|Y],Z,W) :- list_member(X,Z),list_union(Y,Z,W).
list_union([X|Y],Z,[X|W]) :- \+ list_member(X,Z), list_union(Y,Z,W).
list_union([],Z,Z).

注意- 在程序中，我们使用了 (\+) 运算符，该运算符用于NOT。

输出

| ?- [list_set].
compiling D:/TP Prolog/Sample_Codes/list_set.pl for byte code...
D:/TP Prolog/Sample_Codes/list_set.pl:6: warning: singleton variables [Head] for list_subset/2
D:/TP Prolog/Sample_Codes/list_set.pl compiled, 9 lines read - 2004 bytes written, 18 ms

yes
| ?- list_union([a,b,c,d,e],[a,e,i,o,u],L3).

L3 = [b,c,d,a,e,i,o,u] ?

(16 ms) yes

| ?- list_union([a,b,c,d,e],[1,2],L3).

L3 = [a,b,c,d,e,1,2]

yes

交叉口操作

让我们定义一个名为list_intersection(L1,L2,L3)的子句，所以这将取L1和L2，并执行交集操作，并将结果存储到L3中。交集将返回两个列表中都存在的元素。所以 L1 = [a,b,c,d,e]，L2 = [a,e,i,o,u]，则 L3 = [a,e]。在这里，我们将使用 list_member() 子句来检查列表中是否存在一个元素。

程序

list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_intersect([X|Y],Z,[X|W]) :-
   list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([X|Y],Z,W) :-
   \+ list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([],Z,[]).

输出

| ?- [list_set].
compiling D:/TP Prolog/Sample_Codes/list_set.pl for byte code...
D:/TP Prolog/Sample_Codes/list_set.pl compiled, 13 lines read - 3054 bytes written, 9 ms

(15 ms) yes
| ?- list_intersect([a,b,c,d,e],[a,e,i,o,u],L3).

L3 = [a,e] ?

yes
| ?- list_intersect([a,b,c,d,e],[],L3).

L3 = []

yes
| ?-

列表上的杂项操作

以下是可以在列表上执行的一些杂项操作 -

偶数和奇数长度操作

在此示例中，我们将看到两个操作，使用它们可以检查列表是否具有奇数个元素或偶数个元素。我们将定义谓词，即 list_even_len(L) 和 list_odd_len(L)。

• 如果列表没有元素，则为偶数长度列表。

• 否则我们将其视为[Head|Tail]，那么如果Tail是奇数长度，则总列表是偶数长度字符串。

• 类似地，如果列表只有一个元素，则该列表为奇数长度列表。

• 如果将其视为[Head|Tail]，并且Tail是偶数长度的字符串，则整个列表是奇数长度的列表。

程序

list_even_len([]).
list_even_len([Head|Tail]) :- list_odd_len(Tail).

list_odd_len([_]).
list_odd_len([Head|Tail]) :- list_even_len(Tail).

输出

| ?- [list_misc].
compiling D:/TP Prolog/Sample_Codes/list_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/list_misc.pl:2: warning: singleton variables [Head] for list_even_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl:5: warning: singleton variables [Head] for list_odd_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl compiled, 4 lines read - 726 bytes written, 20 ms

yes
| ?- list_odd_len([a,2,b,3,c]).

true ?

yes
| ?- list_odd_len([a,2,b,3]).

no
| ?- list_even_len([a,2,b,3]).

true ?

yes
| ?- list_even_len([a,2,b,3,c]).

no
| ?-

列表除法运算

该操作将一个列表分成两个列表，并且这些列表的长度大致相同。因此，如果给定列表是 [a,b,c,d,e]，则结果将是 [a,c,e],[b,d]。这会将所有奇数放置的元素放入一个列表中，并将所有偶数放置的元素放入另一个列表中。我们将定义一个谓词 list_divide(L1,L2,L3) 来解决此任务。

• 如果给定列表为空，则它将返回空列表。

• 如果只有一个元素，则第一个列表将是包含该元素的列表，第二个列表将为空。

• 假设X,Y是从head开始的两个元素，其余的是Tail，所以制作两个列表[X|List1]，[Y|List2]，这些List1和List2通过划分Tail来分开。

程序

list_divide([],[],[]).
list_divide([X],[X],[]).
list_divide([X,Y|Tail], [X|List1],[Y|List2]) :-
   list_divide(Tail,List1,List2).

输出

| ?- [list_misc].
compiling D:/TP Prolog/Sample_Codes/list_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/list_misc.pl:2: warning: singleton variables [Head] for list_even_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl:5: warning: singleton variables [Head] for list_odd_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl compiled, 8 lines read - 1432 bytes written, 8 ms

yes
| ?- list_divide([a,1,b,2,c,3,d,5,e],L1,L2).

L1 = [a,b,c,d,e]
L2 = [1,2,3,5] ?

yes
| ?- list_divide([a,b,c,d],L1,L2).

L1 = [a,c]
L2 = [b,d]

yes
| ?-

最大项目操作

此操作用于从列表中查找最大元素。我们将定义一个谓词list_max_elem(List, Max)，然后这将从列表中找到 Max 元素并返回。

• 如果只有一个元素，那么它将是最大元素。

• 将列表划分为 [X,Y|Tail]。现在递归地找到[Y|Tail]的最大值并将其存储到MaxRest中，并存储X和MaxRest的最大值，然后将其存储到Max中。

程序

max_of_two(X,Y,X) :- X >= Y.
max_of_two(X,Y,Y) :- X < Y.
list_max_elem([X],X).
list_max_elem([X,Y|Rest],Max) :-
   list_max_elem([Y|Rest],MaxRest),
   max_of_two(X,MaxRest,Max).

输出

| ?- [list_misc].
compiling D:/TP Prolog/Sample_Codes/list_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/list_misc.pl:2: warning: singleton variables [Head] for list_even_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl:5: warning: singleton variables [Head] for list_odd_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl compiled, 16 lines read - 2385 bytes written, 16 ms

yes
| ?- list_max_elem([8,5,3,4,7,9,6,1],Max).

Max = 9 ?

yes
| ?- list_max_elem([5,12,69,112,48,4],Max).

Max = 112 ?

yes
| ?-

列表求和运算

在此示例中，我们将定义一个子句 list_sum(List, Sum)，这将返回列表元素的总和。

• 如果列表为空，则 sum 将为 0。

• 将列表表示为[Head|Tail]，递归求尾部之和并将其存储到SumTemp中，然后设置Sum = Head + SumTemp。

程序

list_sum([],0).
list_sum([Head|Tail], Sum) :-
   list_sum(Tail,SumTemp),
   Sum is Head + SumTemp.

输出

yes
| ?- [list_misc].
compiling D:/TP Prolog/Sample_Codes/list_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/list_misc.pl:2: warning: singleton variables [Head] for list_even_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl:5: warning: singleton variables [Head] for list_odd_len/1
D:/TP Prolog/Sample_Codes/list_misc.pl compiled, 21 lines read - 2897 bytes written, 21 ms

(32 ms) yes
| ?- list_sum([5,12,69,112,48,4],Sum).

Sum = 250

yes
| ?- list_sum([8,5,3,4,7,9,6,1],Sum).

Sum = 43

yes
| ?-

对列表进行合并排序

如果列表是 [4,5,3,7,8,1,2]，则结果将为 [1,2,3,4,5,7,8]。执行合并排序的步骤如下所示 -

• 获取列表并将它们分成两个子列表。这种分割将递归地执行。

• 按排序顺序合并每个拆分。

• 这样整个列表就会被排序。

我们将定义一个名为 mergesort(L, SL) 的谓词，它将接受 L 并将结果返回到 SL 中。

程序

mergesort([],[]).    /* covers special case */
mergesort([A],[A]).
mergesort([A,B|R],S) :-
   split([A,B|R],L1,L2),
   mergesort(L1,S1),
   mergesort(L2,S2),
   merge(S1,S2,S).
   
split([],[],[]).
split([A],[A],[]).
split([A,B|R],[A|Ra],[B|Rb]) :-
   split(R,Ra,Rb).
merge(A,[],A).
merge([],B,B).
merge([A|Ra],[B|Rb],[A|M]) :-
   A =< B, merge(Ra,[B|Rb],M).
merge([A|Ra],[B|Rb],[B|M]) :-
   A > B, merge([A|Ra],Rb,M).

输出

| ?- [merge_sort].
compiling D:/TP Prolog/Sample_Codes/merge_sort.pl for byte code...
D:/TP Prolog/Sample_Codes/merge_sort.pl compiled, 17 lines read - 3048 bytes written, 19 ms

yes
| ?- mergesort([4,5,3,7,8,1,2],L).

L = [1,2,3,4,5,7,8] ?

yes
| ?- mergesort([8,5,3,4,7,9,6,1],L).

L = [1,3,4,5,6,7,8,9] ?

yes
| ?-