Custom reverse of a list in Prolog

Question

Hello,

I am trying to write a predicate that given the following list in Prolog:

[[1,a,b],[2,c,d],[[3,e,f],[4,g,h],[5,i,j]],[6,k,l]]

will produce the following list:

[[6,k,l],[[5,i,j],[4,g,h],[3,e,f]],[2,c,d],[1,a,b]]

As you can see I would like to preserve the order of the elements at the lowest level, to produce elements in the order 1, a, b and NOT b, a, 1.

I would also like to preserve the depth of the lists, that is, lists that are originally nested are returned as such, but in reverse order.

I have managed to achieve the desired order with the following code, but the depth is lost, i.e. lists are no longer nested correctly:

accRev([F,S,T],A,R) :- F \= [_|_], S \= [_|_], T \= [_|_], 
                                 accRev([],[[F,S,T]|A],R).
accRev([H|T],A,R) :- accRev(H,[],R1), accRev(T,[],R2), append(R2,R1,R).
accRev([],A,A).
rev(A,B) :- accRev(A,[],B).

I would appreciate help in correcting the code to preserve the correct nesting of lists. Thanks!

Answer 1

Two suggestions. First, here's one (rev_lists/2) which uses a bunch of SWI-PROLOG built-ins:

rev_lists(L, RL) :-
    forall(member(M, L), is_list(M)), !,
    maplist(rev_lists, L, L0),
    reverse(L0, RL).
rev_lists(L, L).

This one works by testing if all elements of a list L are themselves lists (M); if so, it will recursively apply itself (via maplist) over all individual sub-lists, else it will return the same list. This has the required effect.

Secondly, here's rev_lists/2 again, but written such that it doesn't rely on built-ins except member/2 (which is common):

rev_lists(L, RL) :-
    reversible_list(L), !,
    rev_lists(L, [], RL). 
rev_lists(L, L).

rev_lists([], Acc, Acc).
rev_lists([L|Ls], Acc, R) :-
    (   rev_lists(L, RL), !
    ;   RL = L
    ),
    rev_lists(Ls, [RL|Acc], R).

reversible_list(L) :-
    is_a_list(L),
    \+ (
        member(M, L),
        \+ is_a_list(M)
    ).

is_a_list([]).
is_a_list([_|_]).

It's basically the same strategy, but uses an accumulator to build up reverse lists at each level, iff they are comprised exclusively of lists; otherwise, the same list is returned.