Deep Reverse in PROLOG - Lists

Question

Hey I'm trying to create a predicate for the generating of a deep reverse on nested Lists in PROLOG.

Currently I got this predicate

reverse(L,A) :- rev(L,[], A).
rev([],A,A).
rev([H|L],R,A) :- rev(L,[H|R],A).

The result looks like this:

reverse([1,2,3],A).
A = [3, 2, 1].

reverse([[0,1],2,3],A).
A = [3, 2, [0, 1]].

The problem is, that the inner List is not reversed. It should look like this:

reverse([[0,1],2,3],A).
A = [3, 2, [1, 0]].

reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],A).
A = [12,11,[10,9],[8,[7,6],5,4,3],2,1].

Thanks for any help.

Answer 1

To keep things as simple as possible, we could add a test if the current element being checked is a list or not. If it is indeed a list, then its elements should be reversed as well. So in code:

my_reverse(L,R) :- rev(L,[],R).

rev([],A,A).
rev([H|T],A,R) :-
    ( is_list(H) ->        % If H is a list
      rev(H,[],X),         %   then reverse H as well
      rev(T,[X|A],R)
    ;
      rev(T,[H|A],R)
    ).

Also, not that it really matters, just to try and avoid confusion, note how I used A and R for respectively Accumulator and Result. In your code they are currently swapped, which -for me personally- can be a bit confusing, especially when predicates become longer and more complex.

Anyway, let's look at the queries you provided:

?- my_reverse([[0,1],2,3],R).
R = [3, 2, [1, 0]].

?- my_reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],R).
R = [12, 11, [10, 9], [8, [7, 6], 5, 4, 3], 2, 1].

And some general queries:

?- my_reverse(L,R).
L = R, R = [] ;
L = R, R = [_G2437] ;
L = [_G2437, _G2443],
R = [_G2443, _G2437] ;
L = [_G2437, _G2443, _G2449],
R = [_G2449, _G2443, _G2437] ;
L = [_G2437, _G2443, _G2449, _G2455],
R = [_G2455, _G2449, _G2443, _G2437] 
...

?- my_reverse([[X,Y]|T],R), member(a,T), length(X,2).
X = [_G2588, _G2591],
T = [a],
R = [a, [Y, [_G2588, _G2591]]]
;
X = [_G2594, _G2597],
T = [a, _G2588],
R = [_G2588, a, [Y, [_G2594, _G2597]]]
;
X = [_G2594, _G2597],
T = [_G2582, a],
R = [a, _G2582, [Y, [_G2594, _G2597]]]
...

Note however that using this predicate, no termination occurs after finding the first answer to the query:

?- my_reverse(X,[X]).
X = [X] ;
...

But since this wasn't a requirement/demand in OP's question, I assumed it to be okay.

EDIT:

Please read @mat's answer as a follow-up to this problem.