Is there a cut-less way to implement same_length/3?

Question

Say I want to assert that three lists are of the same length. I could do something like this:

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

This does the right thing when either First or Second are instantiated. It also works when all three arguments are instantiated! However, a call like length(Third, 3), same_length(First, Second, Third) causes it to return the correct answer (all three lists have length 3) with a choicepoint, then loop forever generating solutions which will never match.

I've written a version which I believe does the right thing in every situation:

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) ).

I keep hearing about how the cut should be avoided when at all possible, is it possible to avoid it here?

As a bonus question, I think these are green cuts, since the final predicate is fully relational, is this true?

Answer 1

Why not define same_length/3 in the same way same_length/2 is usually defined?

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

Works nicely when called with all arguments unbound:

?- 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] ;
...

No spurious choice-point or non-terminating backtracking in the case you mention:

?- length(L3, 3), same_length(L1, L2, L3).
L3 = [_1420, _1426, _1432],
L1 = [_1438, _1450, _1462],
L2 = [_1444, _1456, _1468].