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.

Answer 2

an additional solution for your problem is to use cut and the built-in predicate "is_list/1" to check if you treat a simple term or a list in the current call. here is the code:

deepReverse(List,R):-deepReverseTail(List,[],R).

deepReverseTail([],Acc,Acc).

deepReverseTail([H|T],Acc,R):-             % when H is a list
     is_list(H),                           % check if it's a list.
     !,                                    % cut the process if not. 
     deepReverseTail(H,[],Hrev),           % reverse this current list
     deepReverseTail(T,[Hrev|Acc],R).      % continue the general recursion

deepReverseTail([H|T],Acc,R):- deepReverseTail(T,[H|Acc],R). % when H is a simple term

the "cut" in the third line make sure you treat only list in this definition, while treating simple terms will be in the next definitions.

an output example:

7 ?- deepReverse([a,[d,f],[],[[k],g]],R)
R = [[g, [k]], [], [f, d], a].

Answer 3

The way you represent your data is called defaulty, because you need a default case when reasoning over it:

• is it a list? → something holds
• otherwise → something else holds.

Such a representation is a rich source of troubles. Consider for example my_reverse/2 from the other answer. The main problem with it is that it prematurely and incorrectly commits to one of the cases, although both cases are still possible:

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

But this answer only holds for the case where X is not a list! This problem leads to the following strange behaviour of the predicate:

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

This mean that even though X is a list, its elements are not reversed!

You should always aim for cleaner representations to distinguish the cases that can arise.

For example, what would you say about the following way to represent your data:

• list(Ls) represents the list Ls
• n(N) represents the number N.

With such a representations, we can distinguish the cases symbolically. I leave this as the starting point for a more declarative solution.