我需要在Prolog中创建一些“谓词列表”。但我并不完全理解为了创建一些可用的谓词,我需要学习的思维方式。
我看了一些流行的教程(也许我没有足够精确地搜索),但我找不到任何教程教我如何使用真正基础的步骤来规划一个算法。
例如…
任务:
编写一个
concat(X,Y,Z).
谓词,它从列表X
和Y
中取元素,并将它们连接到列表Z
中。
我的分析算法:
首先,我定义了我将要连接的元素数量的域(列表
X
和Y
的长度)为非负整数(XCount >= 0 且 YCount >= 0)。然后我为第一个情况创建一个谓词,即 XCount = 0 且 YCount = 0:
concat([],[],[]).
…然后测试它,发现它对第一个情况有效。
接着,我为第二个情况创建一个谓词,即 XCount = 1 且 YCount = 0,如下所示:
concat(X,[],X).
…再次测试它,发现它有一些意想不到的积极结果。
结果:
我可以看到这个算法不仅对 XCount = 1 有效,对 XCount = 0 也有效。所以我可以删除
concat([],[],[]).
,只保留concat(X,[],X).
,因为在谓词concat(X,[],X).
中X = []
与concat([],[],[]).
是相同的。第二个意想不到的结果是,这个算法不仅对 XCount 在 0,1 有效,对所有 XCount >= 0 都有效。
然后我分析域并寻找尚未处理的元素,发现最简单的方法是为 YCount > 0 创建第二个谓词。
记住仅使用 X 作为第一个参数可以覆盖所有 XCount >= 0,我为 YCount = 1 和所有 X 创建了一个情况,即:
concat(X,[Y|_],[Y|X]).
这就是我的算法出现大脑缓冲溢出的地方。
遵循StackOverflow的规则,我提出了精确的问题。
问题:
-
有什么方法可以自己找到答案吗?我指的不是问题的答案,而是我展示的解决方案的算法。换句话说,我的算法的算法。
-
如果你能回答问题1,我将来如何找到这种类型的提示?我的问题是否有特定的名称?
-
我需要多精确 – 我可以尝试实现多少种情况和用什么语言来实现我的算法,这个算法不仅仅是“做”事情,而是“思考”如何规划和创建其他算法。
回答:
列表不是按其中的元素数量定义的。列表是递归定义的,定义为为空,或者是一个元素和剩余元素的对:
list([]).list([_A|B]) :- list(B).
列表可以是相同的:
same_lists([], []).same_lists([A|B], [A|C]) :- same_lists(B, C).
或者一个可以比另一个短,即它的前缀:
list_prefix([], L):- list(L).list_prefix([A|B], [A|C]):- list_prefix(B, C).
前缀结束的地方,后缀开始:
list_split([], L, L):- list(L).list_split([A|B], Sfx, [A|C]):- list_split(B, Sfx, C).
因此,一般的建议是:遵循类型,它们是如何构建的,并根据所有可能的情况分析情况。对于列表来说,它要么是空的,要么是非空的列表。