Prolog:如何执行“检查(a ++ b ++ c ++ d等于d ++ a ++ c ++ b)->是的" [英] Prolog: how to do "check(a++b++c++d equals d++a++c++b) -> yes"

问题描述

让我们定义自定义运算符-设为++，equals

Let's define custom operators - let it be ++,equals

:- op(900, yfx, equals).
:- op(800, xfy, ++).

事实:

check(A equals A).

我尝试做谓词，让它为check/1，它将在以下所有情况下返回true:

I try to make predicate, let it be check/1, that will return true in all following situations:

check( a ++ b ++ c ++ d equals c ++ d ++ b ++ a ),
check( a ++ b ++ c ++ d equals d ++ a ++ c ++ b),
check( a ++ b ++ c ++ d equals d ++ b ++ c ++ a ),
% and all permutations... of any amount of atoms
check( a ++ ( b ++ c ) equals (c ++ a) ++ b),
% be resistant to any type of parentheses

返回

yes

如何在Prolog中实现此功能?(请提供代码段.可以吗?我是否缺少某些内容?)

How to implement this in Prolog? (Code snippet, please. Is it possible? Am I missing something?)

首选Gnu-Prolog，但也可以使用SWI-Prolog.

Gnu-Prolog is preferred, but SWI-Prolog is acceptable as well.

P.S.请把代码当作伪代码"草稿对待，不要在意小的语法问题.

P.S. Please treat code, as draft "pseudocode", and don't care for small syntax issues.

P.P.S'++'才刚刚开始.我想添加更多运算符.这就是为什么我担心将内容列入清单可能不是一个好的解决方案.

P.P.S '++' is just beginning. I'd like to add more operators. That's why I'm afraid that putting stuff into list might be not good solution.

另外，如果可以进行查询，那就很好了(但是，这部分不是必需的，如果您能够回答第一部分，那很好并且足够了)

Additionally, would be nice, if queries would be possible (but, this part is not required, if you are able to answer to first part, it's great and enough)

check( a ++ (b ++ X) equals (c ++ Y) ++ b) )

可能的结果之一(感谢@mat显示其他结果)

one of possible results (thanks @mat for showing others)

X=c, Y=a

我主要是在寻找问题第一部分的解决方案-是/否"检查.

I am looking mostly for solution for first part of question - "yes/no" checking.

带有X，Y的第二部分将是不错的加法. X，Y应该是简单原子.对于上述示例，指定了X，Y的域:domain(X,[a,b,c]),domain(Y,[a,b,c]).

Second part with X,Y would be nice addition. In it X,Y should be simple atoms. For above example domains for X,Y are specified: domain(X,[a,b,c]),domain(Y,[a,b,c]).

推荐答案

您的表示形式称为默认值":为了处理这种形式的表达式，您需要使用默认"大小写，或显式检查atom/1( (不是单调的)-您不能直接使用模式匹配来处理所有情况.因此，请再次考虑您的情况:

Your representation is called "defaulty": In order to handle expressions of this form, you need a "default" case, or explicitly check for atom/1 (which is not monotonic) - you cannot use pattern matching directly to handle all cases. As a consequence, consider again your case:

check( a ++ (b ++ X) equals (c ++ Y) ++ b) )

您说这应该回答X=c, Y=a.但是，它也可以回答X = (c ++ d), Y = (a ++ d).是否应该也出现这种解决方案?如果不是这样，它将不是单调的，因此会使有关程序的声明式调试和推理大大复杂化.在您的情况下，将此类表达式表示为列表是否有意义?例如，[a，b，c，d]等于[c，d，b，a]?然后，您可以简单地使用库谓词permutation/2来检查此类表达式"的相等性.

You say this should answer X=c, Y=a. However, it could also answer X = (c ++ d), Y = (a ++ d). Should this solution also occur? If not, it would not be monotonic and thus significantly complicate declarative debugging and reasoning about your program. In your case, would it make sense to represent such expressions as lists? For example, [a,b,c,d] equals [c,d,b,a]? You could then simply use the library predicate permutation/2 to check for equality of such "expressions".

当然也可以使用默认表示形式，并且在许多情况下，它们对于用户来说可能更方便(例如Prolog源代码本身，带有目标的默认表示法或Prolog算术表达式).您可以使用非单调谓词(例如var/1和atom/1)，还可以使用术语检查谓词(例如functor/3和(= ..)/2)来系统地处理所有情况，但它们通常会阻止或至少妨碍良好的声明性解决方案可以全方位用于测试并生成所有案例.

It is of course also possible to work with defaulty representations, and for many cases they might be more convenient for users (think of Prolog source code itself with its defaulty notation for goals, or Prolog arithmetic expressions). You can use non-monotonic predicates like var/1 and atom/1, and also term inspection predicates like functor/3 and (=..)/2 to systematically handle all cases, but they usually prevent or at least impede nice declarative solutions that can be used in all directions to test and also generate all cases.

这篇关于Prolog:如何执行“检查(a ++ b ++ c ++ d等于d ++ a ++ c ++ b)->是的"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！