Prolog问题{lists}

Question

我在用prolog实现代码时遇到了一些问题，因为我觉得很难理解它，因为我习惯于正常编码：

我必须对整数列表进行排序，但它必须保留重复的值。我试着想出一个解决方案，我会用气泡排序，但我不知道如何用prolog来写它。如果有人能一步一步地解释代码并启发我，我真的很感激.

是的，我的另一个问题是排序一个由整数和数字列表组成的列表.我不知道怎么开始这个..。例如：[1、2、4、1、4、3、6、7、10、1、3、9、5、1、1、1、1、7]需要输出[1、2、1、4、4、3、6、1、3、7、9、10、5、1、1、1、1、7]。

我试着写了一些代码但是它根本不起作用，我放弃了.我从网上抄袭了第一个问题，但这对我来说没什么意义.

Answer 1

Prolog 是标准编码

它不是命令式编码，它本质上是递归的。您需要停止使用命令式的思想(告诉计算要做什么)，并且需要启动递归思维 (关于这个主题的一本好书)。

MergeSort是你在这里的朋友。它是一种稳定的递归排序算法，具有良好的性能，非常适合prolog的工作方式。它的工作方式很简单：

1. 根据定义，空列表是有序的。
2. 根据定义，长度1的列表也是有序的。
3. 对于长度> 1的列表，
   • 把列表分成两半，
   • 递归排序每一个，和
   • 把两个现在排序的列表合并在一起。

非那样做不行。

所以，我们需要三件事：

• 将列表划分为两部分的谓词，
• 将两个有序列表合并为一个有序列表的谓词，以及
• 使用这两个助手对列表进行排序的谓词。

分区

划分列表很容易。有两种特殊情况终止递归，另一种是一般情况。特例是微不足道的：

• 空列表([])被划分为2个空列表分区( []、[]、[] )。
• 长度1的列表被划分为自身和空列表:分区(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个有序列表合并为一个有序列表同样很简单。我们有3种终止递归的特例和1种一般情况。特殊情况是一个源列表为空，另一个源列表为空，而两个源列表都为空列表的情况：

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

在一般的递归情况下，两个源列表是非空的，这是一个小技巧(但不多)。你有

• 左脑在右脑之前或等于右头的情况下，及
• 左脑在右脑后核对的情况。

我们可以使用Prolog内置的术语比较的运算符来确定排序顺序：

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 ) .

排序

分类也很容易。有两种终止执行的特殊情况，即空列表和长度为1的列表，这两种情况都是按定义排序的。对于长度大于1的列表，一般的递归情况是

• 划分列表，
• 每一半递归排序，
• 合并两个现在排序的列表

因此：

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)
    .

Whole

你可以在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如此具有表现力和简洁性的主要原因。