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

Help! Data Structure
, ,
1

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!

2

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

3

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 :sweat_smile:

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