Prolog append/3 realization with more determinism?

Question

It is folk knowledge that append(X,[Y],Z) finds the last element Y of the list Z and the remaining list X.

But there is some advantage of having a customized predicate last/3, namely it can react without leaving a choice point:

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

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

Is there a way to realize a different implementation of append/3 which would also not leave a choice point in the above example?

P.S.: I am comparing:

/**
 * append(L1, L2, L3):
 * The predicate succeeds whenever L3 unifies with the concatenation of L1 and L2.
 */
% append(+List, +List, -List)
:- public append/3.
append([], X, X).
append([X|Y], Z, [X|T]) :- append(Y, Z, T).

And (à la Gertjan van Noord):

/**
 * last(L, E, R):
 * The predicate succeeds with E being the last element of the list L
 * and R being the remainder of the list.
 */
% last(+List, -Elem, -List)
:- public last/3.
last([X|Y], Z, T) :- last2(Y, X, Z, T).

% last2(+List, +Elem, -Elem, -List)
:- private last2/4.
last2([], X, X, []).
last2([X|Y], U, Z, [U|T]) :- last2(Y, X, Z, T).

[This here](http://stackoverflow.com/a/12710995/772868) is related, but does not solve the problem. — false, Feb 28 '15 at 13:56
Different Prolog implementations have a slight variation on `append/3`. In GNU Prolog, for example, the query, `append(Y, [X], [1,2,3]).` yields `X = 3, Y = [1,2]` without leaving a choice point. I think, though, that the source calls a C function to implement it. — lurker, Feb 28 '15 at 17:08
@lurker: `Ys=[z|Ys], append(Xs, Ys, []), false` loops in GNU! Quelle bonne surprise ! Arf-arf! — false, Feb 28 '15 at 19:36

score 0 · Answer 1 · answered Mar 02 '15 at 13:13

One way to do it is to use foldl/4 with the appropriate help predicate:

swap(A, B, B, A).

list_front_last([X|Xs], F, L) :-
    is_list(Xs),
    foldl(swap, Xs, F, X, L).

This should be it:

?- list_front_last([a,b,c,d], F, L).
F = [a, b, c],
L = d.

?- list_front_last([], F, L).
false.

?- list_front_last([c], F, L).
F = [],
L = c.

?- Ys = [y|Ys], list_front_last(Ys, F, L).
false.

Try to see if you can leave out the is_list/1 from the definition.

`list_front_last(Xs, [a], L)` fails but should succeed – false Mar 02 '15 at 13:19 — false, Mar 02 '15 at 13:19

score 0 · Answer 2 · answered Nov 23 '22 at 19:15

As I posted:

append2(Start, End, Both) :-
    % Preventing unwanted choicepoint with append(X, [1], [1]).
    is_list(Both),
    is_list(End),
    !,
    append(Start, End, Both),
    !.
append2(Start, End, Both) :-
    append(Start, End, Both),
    % Preventing unwanted choicepoint with append(X, Y, [1]).
    (End == [] -> ! ; true).

Result in swi-prolog:

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

Prolog append/3 realization with more determinism?

2 Answers2

Linked