prologappend

Pure append/3 for mode (-,+,+) that wouldn't leave a Choice Point


The usually append/3 is pure, but it leaves a choice point for mode (-,+,+):

?- append(X, [3], [1,2,3]).
X = [1, 2] ;
false.

That thee is a choice point in the above result is seen in that for example SWI-Prolog offers the prompt and then ";" delivers false. I came up with this solution to avoid the choice point:

append2(X, Y, Z) :-
   reverse(Z, H),
   reverse(Y, J),
   append(J, K, H),
   reverse(K, X).

This new append2/3 doesn't leave a choice point anymore:

?- append2(X, [3], [1,2,3]).
X = [1, 2].

But are there better solutions than the reverse/2 cludge? Note, that there is a predicate last/3 which could be used for the example with only one element removed from the end. But the mode (-,+,+) should work for arbitrary long lists in the second argument.


Solution

  • Your append2 doesn't leave choice point for (-, +, +) mode but introduces them for other modes. I do not know if it is possible to write it without checking the mode of operation using var/1 or something.

    Here is a comment from the mercury library manual regarding the mode in question.

    % The following mode is semidet in the sense that it doesn't
    % succeed more than once - but it does create a choice-point,
    % which means it's inefficient and that the compiler can't deduce
    % that it is semidet. Use remove_suffix instead.
    % :- mode append(out, in, in) is semidet.
    

    The remove_suffix predicate is implemented in mercury as follows:

    remove_suffix(List, Suffix, Prefix) :-
        list.length(List, ListLength),
        list.length(Suffix, SuffixLength),
        PrefixLength = ListLength - SuffixLength,
        list.split_list(PrefixLength, List, Prefix, Suffix).