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

So are You saying in Prolog I cannot make a doubly linked list , instead I have to use two lists ? Seems kind of strange a doubly linked list is a basic data structure I learned when I was 12 ! — S. Selfial, Jan 27 '19 at 22:50
I have heard of and worked with the difference list . That was why I asked if You are suggesting to use 2 lists . I guess in another question I could come up with a scenario for which I would use a doubly linked list and seek a difference list solution . But I'm pursuing the doubly linked list in prolog as a playground project with no particular aim beyond having the task of implementing a well known data structure in Prolog . — S. Selfial, Jan 27 '19 at 23:12
@S.Selfial one think you have to keep in mind: Prolog is not the same kind of language as imperative languages. It's a different tool altogether. Of course, you can do a doubly (or singly) linked list in many languages. But those language serve a different purpose. A screwdriver makes a terrible hammer. :) Can you do a difference list in C#? Maybe. But it would be very cumbersome. You can do a doubly linked list in Prolog, but first you'd need to invent your own way to "link" since Prolog doesn't do that in the traditional sense. What you'd end up with is something very clunky. — lurker, Jan 28 '19 at 01:56
Why do you need a doubly linked list? It's a data structure used to solve a certain class of problems. If you were to consider such a problem, then either Prolog has another way to solve it, or Prolog may not be as suitable for solving that problem. Many people try to learn Prolog by trying to do in Prolog what they have done in C or other languages and in the same way, which is not a good way to learn Prolog. It's best to forget the other languages entirely and focus on the things Prolog excels at. Can you do a doubly linked list in SQL? — lurker, Jan 28 '19 at 01:59
@lurker "Can you do a doubly linked list in SQL?" . Sure that is easy . The table is named `node` . It has 4 fields. One field is `id` . One field is `previous_id` . One field is `next_id` . One field is `value` . For the first node in the list , the `previous_id` is null . For the last `node` in the list , the `next_id` is null . — S. Selfial, Jan 28 '19 at 07:28
@S.Selfial then you can do the same in Prolog as in SQL. Assert facts in Prolog that look like your SQL table. Done. — lurker, Jan 28 '19 at 11:42
To others: In the question the OP notes `I was attracted to Prolog because I am interested in "logical purity" .`, but then in a comment notes `But I'm pursuing the doubly linked list in Prolog as a playground project with no particular aim beyond having the task of implementing a well known data structure in Prolog .` My view on this question is that the OP knows what they want and is doing it as a self learning exercise. Continued — Guy Coder, Jan 28 '19 at 11:44
Your idea of using a table to make a list is valid, I just wonder how far away from a doubly linked list you can go and still call it that. In my _opinion_, that idea and the answer by @lurker are a bit too far. If a table is a doubly linked list, so is a pair of Prolog lists with the same elements, going the opposite directions. Is that a doubly linked list? Closer (in spirit and in behaviour) than a table, amirite? — User9213, Jan 28 '19 at 12:13
@User9213 I posted my answer in response to the OP's suggestion of a persistent data table being used. But what about it makes it "far away" from the definition? If it's the persistence, then one could say they could assert data in temporary memory. Outside of that, I don't think it drifts from the definition of such a list. It just can't be managed as efficiently as is normally done. — lurker, Jan 28 '19 at 13:05
Just a general, related comment: I'll often see questions on SO such as "How do I do a case statement in Prolog?" or "How do I do a 'for' loop in Prolog?" These kinds of questions assume that Prolog is just another language in which to solve problems in the traditional, imperative ways. With Prolog, you have to think different. And not all computing problems are best solved with Prolog. Some are best solved imperatively with another language. But some problems Prolog handles with ease that are more cumbersome in other languages. I'm upvoting this q because it leads to useful discussion. — lurker, Jan 28 '19 at 14:09
@GuyCoder I have put another question up at this link https://stackoverflow.com/questions/54407104/read-a-list-of-records-and-perform-ongoing-calculations-about-the-previous-recor Maybe you can demonstrate a solution there that uses a difference list as you suggested. — S. Selfial, Jan 28 '19 at 17:20

Paulo Moura · Answer 1 · 2019-01-31T15:21:51.553

3

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

edited Jan 31 '19 at 15:21

answered Jan 27 '19 at 23:33

Paulo Moura

18,373
3
23
33

Thanks for the links . However I don't think this is applicable ; in the same way Guy Coders comments above suggested a difference list ; insomuch as it is a second data structure (the zipper) maintained in correspondence to the list . The advantage of the doubly linked list , IMO , is that with one data structure traversal is enabled backwards (then forwards) . Also , at least in the slides example , it seems that the list must be completely created , to then have a zipper made of it ? i.e. no zlist append . – S. Selfial Jan 28 '19 at 00:09
P.S. logtalk looks way cool , I'm just not using it 'cause trying to avoid OO paradigm whilst learning prolog . I learned a lot about prolog looking at your test cases :-) – S. Selfial Jan 28 '19 at 00:09
@S.Selfial A zipper allows focusing in an element. Thus, there’s no clear semantics for a zlist append predicate. Also note that Logtalk is a _declarative object-oriented logic programming language_ and not an imperative/procedural OOP language. – Paulo Moura Jan 28 '19 at 00:18
@S.Selfial Note that you don't necessarily need to have **both** a list and its zipper. Depending on your application, you can have only the zipper and grow it and shrink it as needed as the predicates that support these operations are pure. – Paulo Moura Jan 28 '19 at 12:51
"you can have only the zipper" . Yes I gathered that from my perusal of your code in the slides example . But when you say "grow it" ,as mentioned in comment above , lacking some kind of append , I don't see how to grow it . – S. Selfial Jan 28 '19 at 15:34
@S.Selfial Note that pure predicates are provided to insert an element before or after the current element. – Paulo Moura Jan 28 '19 at 15:42
I have put another question up at this link https://stackoverflow.com/questions/54407104/read-a-list-of-records-and-perform-ongoing-calculations-about-the-previous-recor Maybe you can demonstrate a solution there that uses LogTalk and a zipper as you suggested. – S. Selfial Jan 28 '19 at 17:21

score 2 · Answer 2 · answered Jan 28 '19 at 06:22

2

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?

answered Jan 28 '19 at 06:22

User9213

1,316
6
12

@GuyCoder There are two distinct answers to OP's question in what I've written. If this is not good enough for you, then just vote as you like, as you must. I don't care about up- or downvotes. – User9213 Jan 28 '19 at 11:57
@GuyCoder yeah right. A doubly-linked list is a concrete data structure that is (probably) impossible to implement in pure Prolog. A queue, for example, is an abstract data type which can have many different implementations (between the answers here, at least 4!). This does not make OP's question any easier to answer, nor does it make me care more about your reasons for downvoting. – User9213 Jan 28 '19 at 12:00
1

You are right a queue is sometimes what a doubly linked list is used for. But I had in mind something more capable. You asked for a use case and I put one here https://stackoverflow.com/questions/54407104/read-a-list-of-records-and-perform-ongoing-calculations-about-the-previous-recor I loook forward to seeing your solution there! – S. Selfial Jan 28 '19 at 17:36

score 2 · Answer 3 · answered Jan 28 '19 at 11:52

2

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.

answered Jan 28 '19 at 11:52

lurker

56,987
9
69
103

2

Just to make sure we are on the same page here: I liked your answer, +1 and all that stuff. But it really cannot be called a doubly linked list in good faith. Somewhere deep in the Prolog VM there might be something of that kind going on, or maybe not, but this is beside the point. A "linked list" is a very well known and understood low-level data structure, and _emulating it_ using a much higher abstraction is of course fine but not the same. – User9213 Jan 28 '19 at 13:14
@User9213 thanks, and I understand. I don't think the persistent data structure is emulating a linked list. It's just a different storage method. I would certainly agree that it doesn't have the intended efficiency, but I don't think it makes it any less a "linked list". I suppose we would need to point to a strict definition of a "linked list" to resolve that question, though. I see where you are coming from in your definition. Your posted answer digs into the issue I was merely scratching at, which is: what is the actual use case, and what's the correct Prolog approach? – lurker Jan 28 '19 at 13:57
@lurker This seems like a good option to explore. But lots to work out. For example: how is the `id` assigned? And how does a subsequent record find out the `id` of the previous record so that it can link back to it? In SQL I can make `id` an auto-increment so that the `id` is assigned by the database. When I insert the record I can get that `id` as the RETURNING of my query and use that `id` for the subsequent record. Is there similar capability offered by Prolog when asserting facts into the database? Or is there some other way of doing it? – S. Selfial Jan 28 '19 at 17:33
@lurker Maybe a solution to https://stackoverflow.com/questions/54407104/read-a-list-of-records-and-perform-ongoing-calculations-about-the-previous-recor can demonstrate this approach. – S. Selfial Jan 28 '19 at 17:34
@S.Selfial I agree, there's lots to work out. *How is the id assigned*? That's totally up to you. Prolog is, in a way, a very simple language with some deep consequences. In its simplicity, it is sort of low level. You define what various arguments and atoms mean, and you write code to reason with them accordingly. The ultimate solution may not be very efficient. But as I said before, paraphrasing: the question of "How do I make a doubly linked list in Prolog?" is an X-Y problem. :) – lurker Jan 28 '19 at 17:45
@lurker if it pleases you can you tell me what is an "X-Y problem"? – S. Selfial Jan 28 '19 at 17:51
1

Found it . An "X-Y problem" is when for a problem "X" there has been an attempt at a solution "Y" and the user asks a specific question about why "Y" is not working but does not provide any details or description about "X". The undesirable aspect of that is that the specific problem encountered with attempted solution "Y" might not even be relevant to a good solution for the real problem "X". – S. Selfial Jan 28 '19 at 17:57

Daniel Lyons · Accepted Answer · 2019-01-28T23:09:51.727

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]

Ahh that looks perfect ! Please consider adding this usage example to your answer: ` ?- dl2list(NODES,[1,2,3,4]) . NODES = node(1,_A,node(2,_B,node(3,_C,node(4,_D,nil)))) ? ; ` — S. Selfial, Jan 28 '19 at 21:44
@repeat Yes, unfortunately, you cannot create derived lists from a doubly-linked list without recreating the entire thing, unlike the singly linked lists that Prolog uses, where prepending can share the remaining structure. I agree with Paulo that a zipper is probably a better way to accommodate practical usecases than this. But I think you can usually copy a C data structure by using variables in structs the way C would use pointers, even if the utility is lost in the reproduction. — Daniel Lyons, Jan 28 '19 at 23:33

Doubly Linked List in Prolog

4 Answers4

Linked