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?

"Green cuts" are used to improve the efficiency of a program - they simply cut out computation that cannot possibly lead to a solution. "Red cuts" are used to eliminate unwanted solutions. They also improve efficiency, but they also change the possible output of a program. In other words, "green cuts" do not change the program's meaning, but "red cuts" are an integral part of the program producing the desired result. — Enigmativity, Jun 26 '18 at 03:09
I used to worry a lot about situations like this and produced similar-looking predicates with a lot of `var/1` and `ground/1` (which is essentially what you're doing here with `is_list/1`). Invariably, @false would show up and point out a dozen new ways my frankenstein predicate failed to behave in strange situations (lists with instatiated heads and uninstantiated tails, backwards-correctness, etc.) Now I just do the simple thing and hope that debugging it will be easier if I stumble into a strange instantiation pattern in practice. — Daniel Lyons, Jun 26 '18 at 05:31
By the way, I really enjoy your questions, please continue to ask them! — Daniel Lyons, Jun 26 '18 at 05:33
Terminologyproblem: You are using the word uninstantiated when you mean instantiated! — false, Jun 26 '18 at 06:43
@DanielLyons: Please note that such "strange situations" happen typically, when an explanation is generated for (say) failure. You then search for some maximum, like a maximal generalization such that certain properties still hold. If your definitions break in that respect you are just put onto a wrong trail. — false, Jun 26 '18 at 17:50
@false, " You are using the word uninstantiated when you mean instantiated! " I've double-checked my post and I don't see where I'm using "uninstantiated" wrongly, where am I messing up? — num1, Jun 26 '18 at 18:10
@false, `same_length([_|_], _, []).`, hehe, just as Daniel predicted. You're very right! How did you come up with this, what was your intuition that helped you find this? — num1, Jun 26 '18 at 18:11
@DanielLyons thanks for the encouragement, hopefully my questions will slowly become more interesting ;) — num1, Jun 26 '18 at 18:13
@num1: Example: *This does the right thing when either First or Second are uninstantiated.* Counterexample: `same_length(_,[_|_],[]).` does not fail but loops. — false, Jun 26 '18 at 18:25
@num1: You already accepted an answer, so I assume that is what you wanted as answer. I rather would write `maplist(\_^_^_^true, Xs, Ys, Zs)` in stead. — false, Jun 26 '18 at 18:55
@false if you post that comment as an answer I'll certainly upvote it, I didn't think there might be an even shorter answer. — num1, Jun 26 '18 at 19:53
@num1 it should've been https://lpaste.net/4663831766123937792. then `same_length([_|_], _, []).` terminates. — Will Ness, Jul 12 '18 at 07:55

score 6 · Accepted Answer · answered Jun 26 '18 at 06:13

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

I'm fighting a strong urge to curse here because, wow, how could I have missed such a simple solution. Yeah, this is clearly the right way, thank you. — num1, Jun 26 '18 at 17:20

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

1 Answers1