Bidirectional reverse/3 wanted

Help! PlDoc
1

For given a list L, append/3 finds all solutions such that append(X, Y, L) succeeds.

% ?- append(X, Y, [a,b]).
%@ X = [],
%@ Y = [a, b] ;
%@ X = [a],
%@ Y = [b] ;
%@ X = [a, b],
%@ Y = [] ;
%@ false.

I expected similar befhaviour of the well known smart_reverse/3

smart_reverse([], X, X).
smart_reverse([A|X], Y, Z):- smart_reverse(X, [A|Y], Z).

However, for a given list L, query smart_reverse(X, Y, L) goes to endless looping.

% ?- smart_reverse(X, Y, [a, b]).
%@ X = [],
%@ Y = [a, b] ;
%@ X = [a],
%@ Y = [b] ;
%@ X = [b, a],
%@ Y = [] ;      <=== looping

There is a simple workaround for this by

non_smart_reverse(X, Y, Z) :-   append(A, B, Z),
	reverse(B, Y).

% ?- non_smart_reverse(X, Y, [a,b]).
%@ Y = [b, a] ;
%@ Y = [b] ;
%@ Y = [] ;
%@ false.

I don’t like help of append here for some reason, and would like to find a more direct solution.

Of course I noticed the query ?- append(X, Y, Z) with variable X, Y, Z goes endless for infinitely many solutions.

I appreciate if someone shows a smart reverse codes in pure prolog without use of append like the above.

2

Add Z as an extra argument, of decreasing size, to fail when empty (thus preventing spiralling off into infinite length):

smarter_reverse(X, Y, Z):-
    smarter_reverse_(X, Y, Z, Z).

smarter_reverse_([], Z, _, Z).
smarter_reverse_([A|X], Y, [_|Z0], Z) :-
    smarter_reverse_(X, [A|Y], Z0, Z).

Result:

?- smarter_reverse(A, B, [a,b]).
A = [],
B = [a, b] ;
A = [a],
B = [b] ;
A = [b, a],
B = [] ;
false.
1 Like
3

Thanks for the genius solution ! That is what I wanted to see, though I could not find it by myself.