# How to use difference lists to implement queues -vs- accumulators and recursion?

**URL:** <https://swi-prolog.discourse.group/t/how-to-use-difference-lists-to-implement-queues-vs-accumulators-and-recursion/5106>\
**Category:** Data Structure\
**Tags:** how-to, list, difference-list\
**Created:** [March 8, 2022, 3:25pm UTC](https://swi-prolog.discourse.group/t/how-to-use-difference-lists-to-implement-queues-vs-accumulators-and-recursion/5106 "2022-03-08T15:25:50Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Hierophantos](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/hierophantos/32/4012_2.png) [@Hierophantos](https://swi-prolog.discourse.group/u/Hierophantos)\
**Post date:** [March 8, 2022, 3:25pm UTC](https://swi-prolog.discourse.group/t/how-to-use-difference-lists-to-implement-queues-vs-accumulators-and-recursion/5106/1 "2022-03-08T15:25:50Z")

</div>

I’m trying to better grok difference lists. I’d like to use them for the below predicate. Currently it’s using recursion with an accumulator. This creates a stack, which reverses the order that’d I’d like them to be in.

```prolog
indices_elems(Is, Ls, Es) :- indices_elems(Is, Ls, [], Es).
indices_elems([], _, Es, Es).
indices_elems([I|Is], Ls, Acc, Es) :-
    nth1(I, Ls, E),
    indices_elems(Is, Ls, [E|Acc], Es).

:- findall(X, between(1,100,X), Xs), indices_elems([7,11,13,97], Xs, Es).
Xs = [1,2,3,...,99,100],
Es = [97,13,11,7].

```

I’ve heard that difference lists create a natural queue, but haven’t been able to figure out how to implement one; and all resources I’ve seen seem to shroud the whole idea in further mystery.

Of course, I could slap a `reverse/2` at the end and be happy that my needs are met, but I’d rather use Prolog to its fullest. And also, I concede that this predicate doesn’t meet full generality. So any help along those lines also appreciated.

Ideally,

```prolog
:- findall(X, between(1,100,X), Xs), indices_elems([7,11,13,97], Xs, Es).

```

would return `Es = [7,11,13,97]` while using a difference list.

Much appreciated!

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [March 8, 2022, 3:42pm UTC](https://swi-prolog.discourse.group/t/how-to-use-difference-lists-to-implement-queues-vs-accumulators-and-recursion/5106/2 "2022-03-08T15:42:24Z")

</div>

Here is a link to an answer on SO that I wrote ages ago: [queue - Difference lists in Prolog and mutable variables - Stack Overflow](https://stackoverflow.com/questions/31918227/difference-lists-in-prolog-and-mutable-variables/31925828#31925828)

Start reading there maybe? Or does it only intensify the mysteriousness?

Edit: I notice that you are using a list as if it had constant-time access when addressed by position in the list (it doesn’t).

---

<div class="post-metadata">

**Author:** ![jamesnvc](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jamesnvc/32/14_2.png) [@jamesnvc](https://swi-prolog.discourse.group/u/jamesnvc)\
**Post date:** [March 8, 2022, 4:37pm UTC](https://swi-prolog.discourse.group/t/how-to-use-difference-lists-to-implement-queues-vs-accumulators-and-recursion/5106/3 "2022-03-08T16:37:56Z")

</div>

Figuring out how to pass things through difference lists is certainly tricky, it always takes me a minute to figure out, even after doing so a bunch 😅

Here’s your code, slightly modified to build the list in-order, using a difference list:

```prolog
indices_elems(Is, Ls, Es) :-
    indices_elems(Is, Ls, Es, Es). % 1
indices_elems([], _, _, []). % 2
indices_elems([I|Is], Ls, Acc, Es) :-
    nth1(I, Ls, E),
    Es = [E|Es1], % 3
    indices_elems(Is, Ls, Acc, Es1).

```

The key things to note:

1. we pass in the same variable twice, which is our empty difference list; since it’s empty, there’s no difference.
2. In our end condition, we unify the tail of our difference list with `[]`, “closing” it.
3. The key step: We unify the tail of the list with the new value and keep a new “hole” which will serve as the new tail of the difference list, which we pass along in the recursive step.

Running the test again now yields the expected `[7,11,13,97]`.

Hope that helps shed a little bit of light!