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

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] 

Answer 2

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 3

This is a question that keeps on popping up. You really need to explain what you are attempting to do with this doubly linked list. I am very tempted to file this yet again into my collection of delightful XY problem exhibits.

The popular opinion on the topic is that "the easiest way to get to the real problem is usually asking Why five times".

So: Why do you need a doubly linked list? Are you implementing a queue? A sorted list you want to traverse both ways? Something else?

And to make this more of a real answer:

If you use a normal list, you can reverse it whenever you need to have its other end.

If you need a queue that can be pushed into from both ends and popped from one end, you can use a Prolog queue:

queue_empty(q(0, Q, Q)).
queue_back(q(N, Q, [X|Q0]), X, q(s(N), Q, Q0)).
queue_front(q(N, Q, Q0), X, q(s(N), [X|Q], Q0)).

It really depends though, why do you need the doubly linked list? What is your use case?

Answer 4

As discussed in the comments to the original question, as in SQL, you can assert facts in Prolog that can be uses as a linked list:

head_node(Id).
node(Id, Data, LeftId, RightId).

You can designate the atom nil as your null value.

As a very simple example:

head_node(a).

node(a, 123, nil, c).
node(b, 214, c, nil).
node(c, 312, a, b).

You can then write predicates to handle this data:

remove_node(NodeId) :-
    node(NodeId, _, LeftId, RightId),
    ...

The rest of ... can be written with retract, assertz, etc. However, as Guy Coder points out in his comments, this lacks logical purity, which seems to be the original pursuit. The data structure is cumbersome to use and, as I mentioned in the comments, it's best to find a more suitable Prolog-esque way to solve a given problem rather than assume it must be solved using a pattern that is more suitable for a different type of language.