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