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

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.

``````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,

``````:- 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!

Here is a link to an answer on SO that I wrote ages ago: queue - Difference lists in Prolog and mutable variables - Stack Overflow

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).

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:

``````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!

1 Like