CODEWITHSUNDEEP
prolog
Vlad Tamas
Vlad Tamas

Reputation: 33

reverse an incomplete list in prolog

I was searching but I found nothing about how to reverse an incomplete list in prolog. Here is what I did:

incomplete_reverse([L|T],Res):-nonvar(L),!,incomplete_reverse(T,Res1),
                           append(Res1,[L],Res).
incomplete_reverse(L,L):-var(L).

This just reverses the list, but I need it to be deterministic and the reversed list must be also an incomplete list. How can I do that?

Upvotes: 2

Views: 1004

Answers (1)

Paulo Moura
Paulo Moura

Reputation: 18663

My first suggestion is that you get acquainted with difference lists and their applications, if not already. In a nutshell, a difference list is an open list where you keep track of the open end. For example, an empty list can be represented by Tail-Tail. A list with three elements, say, the atoms a, b, and c, can be represented as [a,b,c| Tail]-Tail. This allows e.g. O(1) appending of two lists and adding an element to the end of the list.

But going back to your question, here is some code for you to play with:

reverse_open_list([Element| Rest], Stack, [Element| Stack]) :-
    var(Rest),
    !.
reverse_open_list([Element| Rest], Stack, Reverse) :-
    reverse_open_list(Rest, [Element| Stack], Reverse).

A sample query:

?- reverse_open_list([a,b,c|_], Tail, Reverse).
Reverse = [c, b, a| Tail].

As the open tail is also returned, you can trivially go from the reversed list to a difference list.

Upvotes: 2

Related Questions