1

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.

3 Answers3

2

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).
rajashekar
  • 3,460
  • 11
  • 27
  • So would need to first introduce split_list/4. I think I understand what it is supposed to do. But I guess this here would also work: list.length(Prefix, PrefixLength), append(Prefix, Suffix, List). –  Dec 18 '20 at 09:58
  • Yes `split_list` does what you think, but it is implemented more proceduraly than declaratively. It deconstructs on the PrefixLength. – rajashekar Dec 18 '20 at 10:05
2

But are there better solutions than the reverse/2 kludge?

Better solutions there are, yet not optimal ones:

:- use_module(library(reif)).

append2u(Xs, Ys, Zs) :-
   if_(Ys = Zs,
      Xs = [],
      ( Xs = [X|Xs1], Zs = [X|Zs1], append2u(Xs1, Ys, Zs1) )
   ).

?- append2u(Xs, [3], [1,2,3]).
   Xs = [1,2].

Library reif is built-in in Scryer and also available for SICStus and SWI.

Even the query ...

?- append2u(Xs, Ys, Ys).
   Xs = [].

... now works!

Note that equivalence to append/3 requires the occurs check to be enabled. In a system with rational trees (and thus no occurs check) we get more answers than the single solution:

?- append(Xs, Ys, Ys).
   Xs = []
;  Xs = [_A], Ys = [_A|Ys]        % infinite list Ys = [_A,_A,_A, ...]
;  Xs = [_A,_B], Ys = [_A,_B|Ys]  % infinite list Ys = [_A,_B,_A,_B,_A,_B, ...]
;  ...

Nevertheless,

?- append2u([], Ys, Zs).
   Ys = Zs
;  false.

which is commonly determinate.

However, the termination property is still in tact! In fact append2u/3 terminates a bit better than the common append/3 as illustrates the first case above.

false
  • 10,264
  • 13
  • 101
  • 209
  • Please refer to the query append2u(Xs, Ys, Ys): If that query is already determinate, then (-,+,+) will be determinate, too! – false Dec 18 '20 at 18:02
  • @MostowskiCollapse: I added now your original query. – false Dec 18 '20 at 18:06
  • "if-then-else is not pure." ? Please produce an example where if_/3 is not pure! – false Dec 18 '20 at 18:08
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/226145/discussion-between-mostowski-collapse-and-false). –  Dec 18 '20 at 18:12
  • See edit for the source code you demanded. – false Dec 18 '20 at 18:13
  • @MostowskiCollapse: It seems we do not agree on what pure means. To my understanding, my answer is indeed an answer to your question. – false Dec 18 '20 at 20:49
  • So please produce a case where mode (-,+,+) is not determinate in above implementation. – false Dec 18 '20 at 20:50
  • @MostowskiCollapse: DEC10 style modes refer to **each** instance of the goal. Thus, + effectively implies that the list is of fixed length. Thus, the mode cannot be read alone but always must be accompanied with its actual implementation. – false Dec 18 '20 at 21:06
  • It is not directly an instance. But a subgoal is. – false Dec 18 '20 at 22:17
  • append2u with library(reif) doesn't perform. Try length(P,100), length(Q,200), append(X,P,Q). Its extremly slow, because of the repeatedly comparison Ys = Zs. See timing results in my answer. Looks your pure beautiful, is rather some pure ugly. –  Dec 19 '20 at 07:58
  • Timing is here https://stackoverflow.com/a/65367695/502187 –  Dec 19 '20 at 08:13
  • Yes, it is slower. But it terminates better than your original version! For that you would have to account an infinite speedup. – false Dec 19 '20 at 09:18
  • There is no difference for mode (-,+,+). Both terminate. Please read the question carefully. There are two approaches for the problem of Prolog depth first left selection search. a) your library(reif) b) progamm transformation, like conjunction reordering or even totally rewrite append/3. The problem is you try to take one append/3 definition literaly and only tweak it little bit by library(reif). You cannot get that much good results by this approach.Thats like you would be stuck with an insertion sort, and never come up with quick sort. You are just in a local minima. –  Dec 19 '20 at 10:39
0

Just stepped over a further solution with reverse/3,
eliminating the inner append/3.

append3(X, Y, Z) :-
   reverse(Z, H),
   reverse(Y, K, H),
   reverse(K, X).

reverse(X, Y) :-
  reverse(X, [], Y).

reverse([], X, X).
reverse([X|Y], Z, T) :- 
   reverse(Y, [X|Z], T).

Seems to work, no choicepoint.
And is more performant than append2u:

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

?- length(P,100), length(Q,200), 
   time((between(1,40,_),append3(X, P, Q), fail; true)).
% Up 9 ms, GC 0 ms, Threads 8 ms (Current 12/19/20 08:57:49)
Yes

?- length(P,100), length(Q,200), 
   time((between(1,40,_),append2u(X, P, Q), fail; true)).
% Up 875 ms, GC 9 ms, Threads 862 ms (Current 12/19/20 08:57:45)
Yes

But it is also a little dangerous:

?- append3([1], [2,3], X).
X = [1, 2, 3] ;
%%% hangs