Prolog问题{列表}

Question

我在 prolog 中实现代码时遇到了一些问题，因为我发现它有点难以理解，因为我习惯于正常编码:(

我必须对整数列表进行排序，但它必须保留重复的值。我试图想出一个解决方案，我会使用冒泡排序，但我不知道如何在 prolog 中编写它...如果有人可以逐步解释代码并启发我，我将非常感激...

是的，我遇到的另一个问题是对由整数和数字列表组成的列表进行排序...我不知道如何从这个开始...例如：[1, 2, [4 , 1, 4], 3, 6, [7, 10, 1, 3, 9], 5, [1, 1, 1], 7]需要输出[1, 2, [1, 4, 4], 3, 6, [1, 3, 7, 9, 10], 5, [1, 1, 1], 7].

我试着写了一些代码，但它根本不起作用，我放弃了......我从互联网上复制了一些东西来解决第一个问题，但它对我来说真的没有意义......

Answer 1

Prolog 是正常编码

它只是不是命令式[=96=]编码，它本质上是递归的。你需要停止用命令式的方式思考（告诉计算器做什么），你需要开始 thinking recursively（一本关于这个主题的好书。）

MergeSort 是你的朋友。它是一种稳定的递归排序算法，具有高性能并且 well-suited 符合 prolog 的工作方式。它的工作方式很简单：

根据定义，空列表是有序的。

根据定义，长度为 1 的列表也是有序的。

对于长度 > 1 的列表，

将列表分成两半，

对每一个进行递归排序，并且

将两个 now-ordered 列表合并在一起。

仅此而已。

所以，我们需要三样东西：

一个将列表分成两半的谓词，

一个谓词将两个有序列表合并为一个有序列表，并且

使用这 2 个助手对列表进行排序的谓词。

分区

对列表进行分区很容易。有两种终止递归的特殊情况和一种一般情况。特殊情况是微不足道的：

空列表（[]）被分成2个空列表
partition( [] , [] , [] ) .

一个长度为 1 的列表被划分为自身和一个空列表：
partition( [L] , [L] , [] ) .

一般情况下，长度大于 1 的列表不会更复杂。这里，我们只是从列表中取出前2项，分配给左分区，另一分配给右分区，然后我们向下递归处理余数：

partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs).

把它们放在一起，你得到 partition/3:

partition( [] , [] , [] ) . partition( [L] , [L] , [] ) . partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) .

合并

将2个有序列表合并为1个有序列表同样简单。我们有 3 种终止递归的特殊情况和一种一般情况。特殊情况是一个源列表为空而另一个不为空，并且两个源列表均为空列表的情况：

merge( [] , [] , [] ) . merge( [L|Ls] , [] , [L|Ls] ) . merge( [] , [R|Rs] , [R|Rs] ) .

一般的递归情况，其中两个源列表是 non-empty 是一个小技巧（但不多）。你有

左头在右头之前或等于右头的情况，并且

左头在右头后整理的情况

我们可以使用Prolog的in-built operators for the comparison of terms来确定整理顺序：

merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge( Ls , [R|Rs] , Xs ) . merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @> R, merge( [L|Ls] , Rs , Xs ) .

把它们放在一起，你得到 merge/3:

merge( [] , [] , [] ) . merge( [L|Ls] , [] , [L|Ls] ) . merge( [] , [R|Rs] , [R|Rs] ) . merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge( Ls , [R|Rs] , Xs ) . merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @> R, merge( [L|Ls] , Rs , Xs ) .

排序

排序也同样简单。有 2 种终止执行的特殊情况，空列表和长度为 1 的列表，两者都是按定义排序的。一般递归情况，对于长度大于 1 的列表是

对列表进行分区，

对每一半进行递归排序，并且

合并两个 now-sorted 列表

因此：

merge_sort( [] , [] ) . merge_sort( [X] , [X] ) . merge_sort( [X,Y|Zs] , Ys ) :- partition( [X,Y|Zs], L0, R0 ) , merge_sort(L0,Ls), merge_sort(R0,Rs), merge(Ls,Rs,Ys) .

整个辣酱玉米饼馅

您可以 fiddle 在 https://swish.swi-prolog.org/p/SCBlSONF.pl

partition( [] , [] , [] ) . partition( [L] , [L] , [] ) . partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) . merge( [] , [] , [] ) . merge( [L|Ls] , [] , [L|Ls] ) . merge( [] , [R|Rs] , [R|Rs] ) . merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge( Ls , [R|Rs] , Xs ) . merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @> R, merge( [L|Ls] , Rs , Xs ) . merge_sort( [] , [] ) . merge_sort( [X] , [X] ) . merge_sort( [X,Y|Zs] , Ys ) :- partition( [X,Y|Zs], L0, R0 ) , merge_sort(L0,Ls), merge_sort(R0,Rs), merge(Ls,Rs,Ys) .

您可能会注意到，此程序中的大部分工作都包含每个谓词子句头部的模式匹配。这是使 Prolog 如此富有表现力和简洁的重要原因。

Prolog问题{列表}

Prolog problems {lists}

sorting

prolog