当谓词回溯到相同的解决方案时，使用切割是否有意义？

Question

我正在编写一个简单的矩阵库，我偶然发现了一个解决方案，它提供了一个了解切割目的的机会。

boolean_mult(1,1,1).
boolean_mult(1,0,0).
boolean_mult(0,1,0).
boolean_mult(0,0,0).

binary_dot_product([B1],[B2],Solution) :-
    boolean_mult(B1,B2,Solution).
binary_dot_product([1|_],[1|_],1). % computation can end here.
binary_dot_product([_|B1s],[_|B2s],Solution) :-
    binary_dot_product(B1s,B2s,Solution).

从声明性的角度来看，这个解决方案是有意义的。给定两个 1 和 0 的列表，B1 和 B2，如果它们头部的布尔积是 1，那么列表的点积就是 1。否则取它们尾部的点积。单例列表的点积是两个元素的布尔积。

我遇到的问题显示在这个查询中：

?- binary_dot_product([1,0,1],[1,1,1],X).
X = 1 ;
X = 1 ;
X = 1.

我能够回溯三次，从声明的角度来看这是没有意义的。只能有一个点积！不是3！

我可以通过使用 cut轻松解决这个问题：

binary_dot_product([B1],[B2],Solution) :-
    boolean_mult(B1,B2,Solution).
binary_dot_product([1|_],[1|_],1) :- !. 
binary_dot_product([_|B1s],[_|B2s],Solution) :-
    binary_dot_product(B1s,B2s,Solution).

现在：

?- binary_dot_product([1,0,1],[1,1,1],X).
X = 1.

到目前为止，在我的 Prolog 职业生涯中，我已经避免了像瘟疫一样的削减，因为我已经被警告过它们的危险。在这种情况下，虽然我觉得裁员很有意义。

在上面的代码中使用 cut 会得到什么和失去什么？

Answer 1

编辑（因为OP坚持;-）

我正在回答这个问题：

在上面的代码中使用 cut 我得到了什么，失去了什么？

我不确定你会得到什么。如果您不在代码中使用剪切，您将失去提出更一般性问题的能力，而这些问题是免费获得的。

在一般情况下，多次获得相同的正确解决方案强烈表明您的代码（无论是否有削减）要么是多余的，要么是完全错误的。当然，这并不普遍正确，但从经验来看，这通常是正确的。

你不应该“像瘟疫一样避免削减”。需要时应使用剪切，不需要时不应使用。

这个话题太大了，无法回答。每本像样的 Prolog 教科书都会解释剪切并讨论何时需要它们以及为什么需要它们；并运用你的判断力，这会随着你的编程而改进。

然而：如果你的程序在没有削减的情况下是不正确的，削减将无法修复它。

考虑一下这些问题。

1. 给定两个布尔向量，它们的点积是多少？

2. 实现具有三个参数的谓词。前两个参数是布尔向量，第三个参数是点积。

在 Prolog 领域，第二个问题假设您可以提出诸如“给定一个向量和点积，另一个向量是什么？”之类的问题。您当前的实现之一可以做到这一点吗？你会问这样的问题吗？即使你不认为你会问这样的问题，鉴于你可以做到，你能想出它的用途吗？你知道这是怎么回事吗？

现在，你的代码。它存在一些问题（例如，参见 Isabelle Newbie 刚刚发表的评论）。

这不会给出错误的结果：

:- module(boolean, [add/3, mult/3, dot_product/3]).

add(1,1,1).
add(1,0,1).
add(0,1,1).
add(0,0,0).

mult(1,1,1).
mult(1,0,0).
mult(0,1,0).
mult(0,0,0).

dot_product(V1, V2, P) :-
    same_length(V1, V2),
    maplist(mult, V1, V2, [H|T]),
    foldl(add, T, H, P).

使用它：

?- use_module(boolean).
true.

?- dot_product([1,0,1],[1,1,1],P).
P = 1 ;
false.

?- dot_product([1, 1], [1, 0], Product).
Product = 1 ;
false.

?- dot_product([1, 1], V2, 1).
V2 = [1, 1] ;
V2 = [1, 0] ;
V2 = [0, 1] ;
false.

?- dot_product(V1, V2, 1).
V1 = V2, V2 = [1] ;
V1 = V2, V2 = [1, 1] ;
V1 = [1, 1],
V2 = [1, 0] ;
V1 = [1, 0],
V2 = [1, 1] ;
V1 = V2, V2 = [1, 0] ;
V1 = [1, 1],
V2 = [0, 1] ;
V1 = [0, 1],
V2 = [1, 1] ;
V1 = V2, V2 = [0, 1] ;
V1 = V2, V2 = [1, 1, 1] ;
V1 = [1, 1, 1],
V2 = [1, 1, 0] .

?- dot_product(V1, V2, P).
V1 = V2, V2 = [1],
P = 1 ;
V1 = [1],
V2 = [0],
P = 0 ;
V1 = [0],
V2 = [1],
P = 0 ;
V1 = V2, V2 = [0],
P = 0 ;
V1 = V2, V2 = [1, 1],
P = 1 ;
V1 = [1, 1],
V2 = [1, 0],
P = 1 ;
V1 = [1, 0],
V2 = [1, 1],
P = 1 .

EDIT2：在最后一个正确答案之后仍然剩下一个选择点。要摆脱它，您可以使用表格（例如，在 SWI-Prolog 中可用）。制作add/3和mult/3表，如下所示（在定义它们之前）：

:- table add/3, mult/3.

不再有“假”：

?- dot_product([1,0,1],[1,1,1],P).
P = 1.

?- dot_product(V1, [1, 0], 0).
V1 = [0, 1] ;
V1 = [0, 0].

“长度相同”似乎很重要；由于没有削减，您可以使用谓词来“生成并测试”。无论如何，点积仅针对相同长度的向量定义，不是这样吗？

我没有尝试优化代码。正如您在问题中所观察到的，如果论点有根据，您可以走捷径。这将是剪切（或 if-then-else）的一个很好的用途：如果参数是ground，则在任何向量中查找任何“1”；否则，使用通用算法。

要检查地面列表中的“1”，您可以使用memberchk(1, List).