1

我有一个这样的列表，我正在尝试排序：

[(tim,3),(tom,4),(jane,2),(mary,3)]

我想重新排列它，以便它按降序排列：

[(tom,4),(mary,3),(tim,3),(jane,2)]

我有一个谓词提取给定数字的列表：

extractor([],[],[],_).
extractor([(Name, Number)|List], [(Name, Number)|NewList], Extracted, Number):-
   extractor(List, NewList, Extracted, Number),
   !.
extractor([A|List], NewList,[A|Extracted], Number):-
   extractor(List, NewList, Extracted, Number).

所以给定一个数字，它应该给我一个包含这些数字的元素列表，并有一个没有这些元素的提取列表。

然后我把它通过排序。我有一个最高数字，它应该从 0 循环到那个数字，提取那个数字的任何元素。直到我有排序列表。

numberSort([], _, 0).
numberSort(Unsorted, Sorted, HighestNumber):-
   extractor(Unsorted, Sorted, ExtractedList, Counter),
   numberSort(ExtractedList, Sorted, Counter),
   HighestNumber is 1 + Counter.
numberSort(Unsorted, Sorted, HighestNumber):-
   numberSort(Unsorted, Sorted, Counter),
   HighestNumber is 1 + Counter.

但是，当我尝试这个时，它只是经历了一个无限循环。有人可以帮助我并告诉我哪里出错了吗？谢谢，

4

3 回答 3

3

首先，在详细查看您的代码之前，让我们弄清楚关系应该描述什么。你有成对的形式(Name, Number)——顺便说一句，通常 Prolog 代码更喜欢编写Name-Number。并且您想要两个对列表之间的关系，第二个是对按数字降序的排列。

负数呢？看来你没有考虑这种情况。至少， 0 出现在您的程序中，这表明您打算将它作为最高数字，应该列出[].

为什么你的程序循环？您可能希望通过调试器逐步查看“发生”的情况。那么，为什么不呢？试试看！你会看到你看到很多不相关的事情发生。更有效的是使用这样的：

numberSort([], _, 0) :- false。
numberSort(Unsorted, Sorted, HighestNumber) :- false ,
    extractor(Unsorted, Sorted, ExtractedList, Counter) ,
    numberSort(ExtractedList, Sorted, Counter) ,
    HighestNumber 是 1 + Counter。
numberSort(Unsorted, Sorted, HighestNumber) :-
   numberSort(Unsorted, Sorted, Counter), false ,
    HighestNumber 是 1 + Counter。

?- numberSort([(tim,3),(tom,4),(jane,2),(mary,3)], Sorted, H)。

您的程序的这个片段仍然循环，因此您的原始程序也会循环。你不需要看到更多！更糟糕的是：您的程序会循环所有查询！要解决此问题，您必须至少修复剩余可见部分中的某些内容。在您花费了一些时间之后，这可能会让您感到惊讶，extractor/4但无论其定义如何，都会发生此循环。

另一个问题是extractor/4：

| ?- extractor([(tim,3),(jane,4)], Xs, Ys, 3).
Xs = [(tim,3)],
Ys = [(jane,4)] ? ;
no
| ?- extractor([(tim,3),(jane,4)], [], Ys, 3).
Ys = [(tim,3),(jane,4)] ? ;
no

这不是很奇怪吗？第一个查询成功（可能根据您的期望），第二个应该因此失败，但它成功了。罪魁祸首是您在规则末尾放置的切口。我们说，谓词不坚定。我建议以根本不需要任何剪切​​的方式编写此谓词。

于 2013-12-01T21:09:29.420 回答
1

这是调试代码的方法

?- leash(-all),trace,numberSort([(tim,3),(tom,4),(jane,2),(mary,3)],L,N).
   Call: (7) numberSort([ (tim, 3), (tom, 4), (jane, 2), (mary, 3)], _G7370, _G7371)
   ...
   Exit: (8) extractor([ (tim, 3), (tom, 4), (jane, 2), (mary, 3)], [ (tim, 3), (mary, 3)], [ (tom, 4), (jane, 2)], 3)
   Call: (8) numberSort([ (tom, 4), (jane, 2)], [ (tim, 3), (mary, 3)], 3)
    ...
   Call: (11) extractor([], [ (tim, 3), (mary, 3)], _G7590, _G7602)
   Fail: (11) extractor([], [ (tim, 3), (mary, 3)], _G7590, _G7602)
   ...

调用 (8) 似乎对其参数进行了太多实例化，因此提取器失败。纠正代码并不容易，因为我不完全理解逻辑。

我认为应该有一些附加，或者你应该使用差异列表。

OTOH，使用该库的一种更简单的方法。有一个内置的predsort允许指定一个谓词进行比较：

?- predsort(\X^Y^Z^(Y=(A,B),Z=(C,D), (B < D -> X = > ; X = <)), [(tim,3),(tom,4),(jane,2),(mary,3)], L).
L = [ (tom, 4), (tim, 3), (mary, 3), (jane, 2)].

这个“查询”使用 library(lambda) 来构建所需的 arity 3 谓词。

于 2013-12-01T20:06:19.050 回答
-1

CapelliC 有一个非常有用的答案，我认为我实例化的方式有问题。numberSort 谓词有问题。它应该是这样的：

numberSort([], [], 0).
numberSort(Unsorted, Sorted, HighestNumber):-
     Counter is HighestNumber - 1,
     extractor(Unsorted, SemiSorted, ExtractedList, Counter),
     numberSort(ExtractedList, Sorting, Counter),
     append(SemiSorted, Sorting, Sorted), !.
numberSort(Unsorted, Sorted, HighestNumber):-
     Counter is HighestNumber - 1,         
     numberSort(Unsorted, Sorted, Counter).

那应该行得通。如果有人发现它有任何问题，请告诉我。

于 2013-12-01T20:30:28.167 回答