4

假设我想断言三个列表的长度相同。我可以做这样的事情：

same_length(First, Second, Third) :-
  same_length(First, Second),
  same_length(Second, Third).

First当实例化或Second实例化时，这会做正确的事情。当所有三个参数都被实例化时，它也可以工作！然而，调用 likelength(Third, 3), same_length(First, Second, Third)会导致它返回带有选择点的正确答案（所有三个列表的长度均为 3），然后永远循环生成永远不会匹配的解决方案。

我写了一个我相信在任何情况下都能做正确事情的版本：

same_length(First, Second, Third) :-
  /* naively calling same_length(First, Second), same_length(Second, Third) doesn't work,
     because it will fail to terminate in the case where both First and Second are
     uninstantiated.
     by always giving the first same_length/2 clause a real list we prevent it from
     generating infinite solutions */
  ( is_list(First), same_length(First, Second), same_length(First, Third), !
  ; is_list(Second), same_length(Second, First), same_length(Second, Third), !
  ; is_list(Third), same_length(Third, First), same_length(Third, Second), !
    % if none of our arguments are instantiated then it's appropriate to not terminate:
  ; same_length(First, Second), same_length(Second, Third) ).

我一直听说应该尽可能避免切割，这里可以避免吗？

作为一个额外的问题，我认为这些是绿色削减，因为最终谓词是完全相关的，这是真的吗？

4

1 回答 1

6

为什么不按照通常定义same_length/3的方式定义呢？same_length/2

same_length([], [], []).
same_length([_| T1], [_| T2], [_| T3]) :-
    same_length(T1, T2, T3).

在所有参数未绑定的情况下调用时效果很好：

?- same_length(L1, L2, L3).
L1 = L2, L2 = L3, L3 = [] ;
L1 = [_990],
L2 = [_996],
L3 = [_1002] ;
L1 = [_990, _1008],
L2 = [_996, _1014],
L3 = [_1002, _1020] ;
L1 = [_990, _1008, _1026],
L2 = [_996, _1014, _1032],
L3 = [_1002, _1020, _1038] ;
...

在您提到的情况下，没有虚假的选择点或非终止回溯：

?- length(L3, 3), same_length(L1, L2, L3).
L3 = [_1420, _1426, _1432],
L1 = [_1438, _1450, _1462],
L2 = [_1444, _1456, _1468].
于 2018-06-26T06:13:00.647 回答