Есть ли безрезультатный способ реализации same_length / 3? - PullRequest
Новая
       13

Есть ли безрезультатный способ реализации same_length / 3?

0 голосов
/ 26 июня 2018

Скажем, я хочу утверждать, что три списка имеют одинаковую длину.Я мог бы сделать что-то вроде этого: 

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

Это правильно, когда создаются экземпляры First или Second.Это также работает, когда создаются все три аргумента!Однако, вызов типа length(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) ).

Я постоянно слышу о том, как следует избегать порезов, когда это возможно, возможно ли избежать этого здесь?

КакБонусный вопрос, я думаю, что это зеленые сокращения, поскольку последний предикат полностью реляционный, это правда?

1 Ответ

0 голосов
/ 26 июня 2018

Почему бы не определить 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].
...