# Queue or linked list type of data structure in SWI-Prolog that can be accessed from "either end"? **URL:** \ **Category:** Help!\ **Created:** [June 10, 2019, 1:25am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784 "2019-06-10T01:25:40Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [June 10, 2019, 1:25am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/1 "2019-06-10T01:25:40Z")
I’m using: SWI-Prolog version 8.0.2 on Ubuntu Linux 18.04. I need to know if there is a data structure in SWI-Prolog that allows me to emulate a queue or linked list that I can access from “either end”. By either end I mean access the elements linearly from the oldest element to the newest, or conversely, from the newest element to the oldest. My app maintains a history of each transaction with the user. It needs to examine that history but most of the time it just needs to access a few of the most recent transactions, **reading in reverse chronological order** , starting with the newest transaction and iterating towards the oldest. Every now and then it will need to access that history in the opposite direction, from the oldest to the newest. So I need to know what is the SWI-Prolog equivalent of a queue or linked list that one can traverse in either direction? If no such thing exists, I need to know how to get the same effect from the Prolog database. The worst situation is if I have to read from the beginning of the history all the way to the most recent transactions in order to get just those recent transactions. It is most convenient if I can read the elements in reverse chronological order without having to sort them. I don’t know enough about the Prolog database to know in what order elements are stored in the database when you make assertions to the same predicate and subsequently make a query with backtracking upon that predicate. So, if there is no such data structure in SWI-Prolog that does what my app needs here, how can I use `asserta/assertz` to add elements in the correct order so that when I do a query to the predicate, I get the newest element first and upon backtracking, iterate from the newest transaction in a direction iterates progressively towards the oldest element ever asserted to the database? ---
**Author:** ![michaelby](https://avatars.discourse-cdn.com/v4/letter/m/b3f665/32.png) [@michaelby](https://swi-prolog.discourse.group/u/michaelby)\ **Post date:** [June 10, 2019, 6:10am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/2 "2019-06-10T06:10:54Z")
You can use a pair consisting of a list to which you add the transaction at the beginning and a difference list to which you add the transaction at the end. Use the list for reverse chronological traversal and the difference list for chronological. That’s assuming you don’t need to remove any transactions. You probably know this, but it’s generally a bad idea to use the dynamic database unless you absolutely have to. ---
**Author:** ![pmoura](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/pmoura/32/11_2.png) [@pmoura](https://swi-prolog.discourse.group/u/pmoura)\ **Post date:** [June 10, 2019, 6:41am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/3 "2019-06-10T06:41:34Z")
Thus the queue information need to survive backtracking? ---
**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\ **Post date:** [June 10, 2019, 9:15am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/4 "2019-06-10T09:15:25Z")
Queues are something of a nightmare in Prolog, traditionally involving difference lists and incomplete data structures, which are confusingly explained using different notations in different textbooks (worse yet, the notation used in The Art of Prolog doesn’t work at all in SWI Prolog since it uses the escape slash). To sidestep all that, I’d suggest looking at builtin nth1/4 predicate to create enqueue and dequeue predicates ```prolog enqueue(OldQueue, Element, NewQueue) :- length(OldQueue, Length), Idx is Length + 1, nth1(Idx, NewQueue, Element, OldQueue). dequeue(OldQueue, Element, NewQueue) :- length(OldQueue, Length), nth1(Length, OldQueue, Element, NewQueue). ``` ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [June 10, 2019, 11:37am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/5 "2019-06-10T11:37:33Z")
Might be worthwhile to check: [http://www.swi-prolog.org/pldoc/doc/\_SWI\_/library/heaps.pl](http://www.swi-prolog.org/pldoc/doc/_SWI_/library/heaps.pl) ---
**Author:** ![fsaenzperez](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/fsaenzperez/32/50_2.png) [@fsaenzperez](https://swi-prolog.discourse.group/u/fsaenzperez)\ **Post date:** [June 10, 2019, 11:52am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/6 "2019-06-10T11:52:51Z")
> [@michaelby](#): > > You probably know this, but it’s generally a bad idea to use the dynamic database unless you absolutely have to. Not long time ago, I was surprised with how fast the dynamic database was performing. I think that using it depends on the application, and one may reach competitive times when using this database. I’ll try to ellaborate on this when time permits. ---
**Author:** ![michaelby](https://avatars.discourse-cdn.com/v4/letter/m/b3f665/32.png) [@michaelby](https://swi-prolog.discourse.group/u/michaelby)\ **Post date:** [June 10, 2019, 12:05pm UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/7 "2019-06-10T12:05:39Z")
Just a few comments on this. Firstly, OP is asking about traversing the elements from both sides, so a simple queue is not the right data structure. Possibly a deque (double-ended queue) is needed, but I think the requirements are a bit less general. Secondly, there is nothing wrong with using difference lists in a queue data structure. O’Keefe explains in _The Craft of Prolog_ how to use successor arithmetic to keep track of the length of the queue in a pure way, so that you can even prevent the queue from “hallucinating” (his terminology) new elements when you dequeue an element from an empty queue. Thirdly, the code you give is doing enqueue and dequeue at the end of the list, so that what you actually have is a stack. You probably meant to enqueue at the head of the list. Fourthly, the operations you are using are O(N), so you might as well just `append/3` to get to the last element and avoid using `length/2`. Much better would be to use difference lists and have O(1) enqueue and dequeue operations. ---
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [June 10, 2019, 1:26pm UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/8 "2019-06-10T13:26:15Z")
Thanks everyone for your comments. I believe I’ll use a combination of asserta/assertz and a heap (thanks @swi). I will keep a “global” counter in the database to act as the hash key. Then with each transaction I add to history I will: - increment the “global” counter to create a new key. - insert the new history compound term into the heap using the key - `assertz` the key to a predicate named **history\_z** for oldest to newest ordering - `asserta` the key to a predicate named **history\_a** for newest to oldest ordering Then I can just backtrack through either history predicate to get the order I desire. With each solution I will get the hash key and then just do a lookup in the heap to get the actual value. I believe the above solution is a good combination of performance and storage efficiency that is linear in the number of operations necessary to implement it? @michaelby I am familiar with _difference lists_ since the `The Art of Prolog` was the first Prolog book I ever read. But I need this data to be in the **database** since it has to persist across asynchronous transactions with the user. I assume you weren’t indicating that I should save/restore the difference list to the database since that would be a very heavy transaction given how large the history will become over time. ---
**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\ **Post date:** [June 10, 2019, 2:12pm UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/9 "2019-06-10T14:12:28Z")
True, dequeue is the wrong term since I’m refering to removing from the end of the list as opposed to LIFO. The point is that adding and removing things from the ends of lists in Prolog is not very elegant, and using DCGs are generally the best way of handling difference lists. ---
**Author:** ![michaelby](https://avatars.discourse-cdn.com/v4/letter/m/b3f665/32.png) [@michaelby](https://swi-prolog.discourse.group/u/michaelby)\ **Post date:** [June 11, 2019, 6:10am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/10 "2019-06-11T06:10:11Z")
> [@prodog](#): > > @michaelby I am familiar with _difference lists_ since the `The Art of Prolog` was the first Prolog book I ever read. But I need this data to be in the **database** since it has to persist across asynchronous transactions with the user. I assume you weren’t indicating that I should save/restore the difference list to the database since that would be a very heavy transaction given how large the history will become over time. Ah, sorry. I misunderstood. Indeed, I wasn’t suggesting saving and restoring a large data structure to and from the database. It’s possible to thread the Prolog data structure through your code as an argument but it can become very annoying in code that is very I/O heavy or impossible without copying when threads are involved. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [June 11, 2019, 6:30am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/11 "2019-06-11T06:30:21Z")
There are two alternatives: backtrackable global variables allow for keeping a global data structure without argument passing and _engines_ allow sharing such a thing also between threads. Engines are a pretty neat solution to create a global and possible shared resource built around a large complex Prolog term. ---
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [June 11, 2019, 11:00am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/12 "2019-06-11T11:00:15Z")
> [@jan](#): > > Engines are a pretty neat solution to create a global and possible shared resource built around a large complex Prolog term. Are you referring to PEngines Jan, or is this a feature of SWI-Prolog I need to read up on? ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [June 11, 2019, 11:13am UTC](https://swi-prolog.discourse.group/t/queue-or-linked-list-type-of-data-structure-in-swi-prolog-that-can-be-accessed-from-either-end/784/13 "2019-06-11T11:13:30Z")
See [http://www.swi-prolog.org/pldoc/man?section=engines](http://www.swi-prolog.org/pldoc/man?section=engines)