Prolog:怎么做"检查(a ++ b ++ c ++ d等于d ++ a ++ c ++ b) - >是"

Question

让我们定义自定义运算符 - 让它成为++,equals

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

事实上:

check(A equals A).

我尝试制作谓词,让它成为check/1,在以下所有情况下都会返回:

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中实现这一点？(请注明代码片段.有可能吗？我错过了什么吗？)

Gnu-Prolog是首选,但SWI-Prolog也是可以接受的.

PS请将代码视为草稿"伪代码",并不关心小的语法问题.

PPS'++'刚刚开始.我想添加更多运营商.这就是为什么我担心把东西列入清单可能不是一个好的解决方案.

另外

另外,如果可以进行查询会很好(但是,这部分不是必需的,如果你能够回答第一部分,那就太好了)

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

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

X=c, Y=a

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

使用X,Y的第二部分将是很好的补充.在它X中,Y应该是简单的原子.对于X的上述示例域,指定了Y : domain(X,[a,b,c]),domain(Y,[a,b,c]).

Answer 1

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

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]？然后,您可以简单地使用库谓词置换/ 2来检查此类"表达式"的相等性.

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