Prolog append/3 realization with more determinism?

2019-05-26 02:42发布

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

标签: prolog
1条回答
Root(大扎)
2楼-- · 2019-05-26 02:52

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.

查看更多
登录 后发表回答