CODEWITHSUNDEEP
listprologreverse
user3389469
user3389469

Reputation: 11

Prolog: reverse list (sublists included)

I have written the simple code to reverse a typical integer list:

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

? reverse([1, 2, 3], X)
X = [3, 2, 1].

However, I am pretty lost, as I am new to prolog, how to reverse a list that has other sublists within it, such as:

? reverse([1, [2, 3], [1, [3, [2, 4, 5], 1], 2], 5], X).
X = [5, [2, [1, [5, 4, 2], 3], 1], [3, 2], 1].

etc. Any help is appreciated, thanks!

Upvotes: 1

Views: 864

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74197

Without using any built-ins, you can do:

reverse_nested_list( Xs, Rs ) :-
  reverse_nested_list( Xs, [], Rs )
  .

reverse_nested_list( []     , Rs , Rs ) .
reverse_nested_list( [X|Xs] , Ts , Rs ) :-
  is_list(X) ,
  !          ,
  reverse_nested_list(X,[],T) ,
  reverse_nested_list(Xs,[T|Ts],Rs)
  .
reverse_nested_list( [X|Xs] , Ts , Rs ) :-
  reverse_nested_list(Xs,[X|Ts],Rs)
  .

%
% cursory check for list-ness.
% 
is_list(X) :- var(X), !, fail.
is_list([]).
is_list([_|_]).

Easy!

Upvotes: 1

CapelliC
CapelliC

Reputation: 60004

The definition can be made very compact:

deep_reverse(A, B) :- maplist(deep_reverse, A, R), !, reverse(R, B).
deep_reverse(A, A).

I've renamed it to be able to use the library predicate. Generally, I think it's best to avoid redefining library predicates.

Upvotes: 1

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7209

This modification of your code works, but it's clumsy:

reverse([], []).
reverse([X|Y], A) :- reverse(Y, Z), reverse(X, Xrev), append(Z, [Xrev], A), !.
reverse(X, X). % not a list

BTW, reverse([X], [X]). clause in your original code is not needed.

Update thanks to @mbratch comment:

reverse([X|Y], A) :- reverse(Y, Z), reverse(X, Xrev), append(Z, [Xrev], A).
reverse(X, X) :- X \= [_|_]. % X is not a list, or X is an empty list

Upvotes: 1

Related Questions