Doubly Linked List in Prolog

Question

I have been learning Prolog in my spare time for about 8 months to a year and now I am moving on to tackle implementing some of the classic data structures and algorithms .

I am interested in achieving a doubly linked list in Prolog, but quite baffled as to how to proceed . I was attracted to Prolog because I am interested in "logical purity" .

It seems that I am so accommodated to the object-oriented paradigm that beyond the simple I just cannot proceed without it !

For reference by doubly linked list I mean something similar to what is described in this link :

Double Linked List

Answer 1

One possible materialization of a double-linked list in Prolog is to use a zipper. If you're not familiar with the concept, see e.g.

https://en.wikipedia.org/wiki/Zipper_(data_structure)

A zipper allows you to navigate a list backward and forward while providing access to the current element. Thus, it provides functionality common to doubled-linked lists. Logtalk (which you can run with most Prolog compilers) includes library support for zippers. The zipper protocol can be browsed at:

https://logtalk.org/library/zipperp_0.html

This protocol is implemented for lists by the zlist object. You can browse its code at:

https://github.com/LogtalkDotOrg/logtalk3/blob/master/library/zlist.lgt

Note that most predicates are pure with several of them defined by facts. There's also an usage example at:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/slides

Answer 2

What makes it a doubly-linked list is that it has two links rather than one, a reference to the previous and the next item in the list. So we could make a node(Value, Previous, Next) struct and make the list manually like so: A = node(1, nil, B), B = node(2, A, nil).. We could make longer lists the analogous way, just creating more intermediate variables.

Translating that back into a "normal" list would look something like this:

dl2list(node(X, _, nil), [X]).
dl2list(node(A, _, node(X,Y,Z)), [A|Rest]) :- dl2list(node(X,Y,Z), Rest).

This makes no particular use of the "previous" pointer, but you can see it works:

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2list(A, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4] .

We could also build backwards, starting from the end:

dl2listrev(node(X, nil, _), [X]).
dl2listrev(node(A, node(X,Y,Z), _), [A|Rest]) :- dl2listrev(node(X,Y,Z), Rest).

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2listrev(D, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [4, 3, 2, 1] 

To construct a doubly-linked list from a list, you need something a little stronger than either of these:

l2dl(L, DL) :- l2dl(L, DL, nil).

l2dl([X], node(X, Prev, nil), Prev).
l2dl([X,Y|Xs], node(X, Prev, Next), Prev) :- 
    l2dl([Y|Xs], Next, node(X, Prev, Next)).

This you can see working in both directions here:

?- l2dl([1,2,3,4], X), dl2list(X, L).
X = node(1, nil, node(2, _S1, node(3, _S2, _S3))), % where
    _S1 = node(1, nil, node(2, _S1, node(3, _S2, _S3))),
    _S2 = node(2, _S1, node(3, _S2, _S3)),
    _S3 = node(4, node(3, _S2, _S3), nil),
L = [1, 2, 3, 4] 

and here:

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   l2dl(L, A).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4]