首页 文章

Prolog递归列表列表

提问于
浏览 次
2

现在，我不得不尝试定义一个谓词 ascending/1 ，它接受一个列表列表，并确定列表是否按照增加的大小排列在列表列表中 . 我创建了一个帮助谓词 smaller/2 并接收了2个列表，例如A和B'，如果A长度小于或等于B则会成功，否则会失败 . 我的问题是，如何在谓词 ascending/1 中递归调用 smaller/2 ，假设 smaller/2 正确实现？我是prolog的新手，所以语法让我感到困惑 . 到目前为止我有：

%empty list%

ascending([]).
ascending([Z]) :- smaller ([_|Z]), [_,_|Z]).

我试图采取列表列表的头部，并将其与列表列表的第二个头部进行比较 . 我也不想只使用我的帮助器谓词来使用任何其他预定义函数 .

list sorting recursion prolog

1 回答

  • 2

    所以，这是我的答案 - 在此期间出现了a related question .

    在回答原始问题之前，我将查看升序的整数列表 . 原因是：在列表及其元素之间进行区分更为简单 .

    查找描述性名称

    避免命令，因为（纯）Prolog谓词什么都不做 . 或者充其量他们描述关系 . 但他们没有排序或添加或比较 . 在我们的案例中 ascending/1 可能是一个理想的名称， sorted/1 不太理想，因为它有点暗示有人会对事物进行排序 . 因此，周围仍然存在一个微小的imp（强制性实体） .

    给出一些测试用例

    这通常有助于澄清对您的意义 . 永远记住：现在，你的思想很新鲜，所以要努力添加有意义的测试用例 . 以后你会变得疲倦而不那么专注，但让我向你保证：你的Prolog系统永远不会累 . 因此，您可以将这些测试用例放在文件的末尾：

    ?- ascending([1,2]).
?- ascending([1,1,2]).
?- \+ ascending([2,1]).

    从过于笼统的谓词开始

    一个（微不足道的）第一次尝试可能是：

    ascending(_).

    这个定义永远成功！显然太笼统了 . 那么我们如何专注呢？添加单个目标将不起作用 . 但由于它应该是一个列表 - 我们可以从列表的定义开始 .

    ascending([]).
ascending([_E|Es]) :-
   ascending(Es).

    现在，这仍然是一般的，我们想要一个具有某些属性的整数列表 . 所以我们再次需要专门化这个定义 . 我们想要的是 Es = [A,B,C] 目标 A #=< B, B #=< C 持有 .

    :- use_module(library(clpfd)).
ascending([]).
ascending([E|Es]) :-
   E #=< F,
   ascending(Es).

    你有没有看到关于 F 是单身的警告？ Prolog讨厌这些变量，它们经常是错别字 . 从某种意义上讲，Prolog是对的 . 我们应该把 F 与其他东西联系起来 . 它应该是 Es 中的下一个元素 .

    ascending([]).
ascending([E|Es]) :-
   lesseq_than_first(E, Es),
   ascending(Es).

lesseq_than_first(_, []).
lesseq_than_first(E, [F|_]) :-
   E #=< F.

    我们可以“优化”这个定义 . 但是这种形式更好地揭示了它的含义：它是一个列表，元素是相互关联的 .

    升序整数列表非常多 . 但是，列表升序的事实是多么重要，下降列表几乎不能具有相同的定义？如果有太多的名字填满我们超负荷的头脑，这不是浪费我们的宝贵关注吗？

    我们基本上有一系列与 (#=<)/2 互连的 Value 观，这可能是任何其他关系 . 所以我们可以说 chain(#=<, [1,2,3]) 而不是 ascending([1,2,3]) . （顺便说一句：这个名字好吗？或者你有更好的名字？）

    chain(R_2, []).
chain(R_2, [E|Es]) :-
   rel_to_first(R_2, E, Es),
   chain(R_2, Es).

rel_to_first(_R_2, _E, []).
rel_to_first(R_2, E, [F|_]) :-
   call(R_2, E, F).

    通过这个一般定义，我们现在可以回到原始谓词： smaller/2 不是一个理想的名称 . 也许 shorter_than/2 ？

    shorter_than([], _).
shorter_than([_|Es], [_|Fs]) :-
   shorter_than(Es, Fs).

sorted(Ess) :-
  chain(shorter_than, Ess).

    写完之后我意识到我忘了说明另一个好建议：和顶级玩家一起玩吧！但这不符合这个答案......

    回复于

相关问题