Quick basic list questions. Not a test just checking what I believe to be correct

Help! Data Structure
,
1

There are closed list which end with [] and open list which end with a variable, e.g.

Closed list AKA list

?- write_term([a,b,c],[dotlists(true)]).
.(a,.(b,.(c,[])))
true.

Open list AKA Partial list

?- write_term([a,b|T],[dotlists(true)]).
.(a,.(b,_7990))
true.

Then there are difference list, e.g.
[1,2,3,4]-[3,4] or
[1,2|T]-T or
[1,2,3,4|T]-[3,4|T]

?- write_term([1,2,3,4],[dotlists(true)]),
    write_term(" - ",[]),
    write_term([3,4],[dotlists(true)]).
.(1,.(2,.(3,.(4,[])))) - .(3,.(4,[]))
true.

?- write_term([1,2|T],[dotlists(true)]),
    write_term(" - ",[]),
    write_term(T,[dotlists(true)]).
.(1,.(2,_4594)) - _4594
true.

?- write_term([1,2,3,4|T],[dotlists(true)]),
    write_term(" - ",[]),
    write_term([3,4|T],[dotlists(true)]).
.(1,.(2,.(3,.(4,_6812)))) - .(3,.(4,_6812))
true.

Did I make a mistake anywhere?

EDIT

The purpose of this question was

  1. As part of the research for a reply in this post.

  2. In preparation for creating has_type/2 for difference list. Details in this post.

1 Like
2

I can’t escape the feeling that you are making too much out of difference lists. The underlying reason might be that there is a name for them, “difference lists”, and to add to the confusion, there is a lot of teaching material out there where it is written as List-Rest and then the - is like a minus and when we subtract we find the difference between numbers and at some point the brain goes “AHA!”

In the way that OOP has its “design patterns”, Prolog seems to have a few… things? that have names, like:

  • difference lists
  • accumulators
  • green/red/blue/grue etc. cuts

These are basically “patterns”. Other “patterns” either have not-so-popular names, or even lack a name completely. An example of an obscure name for a very common pattern is “lagging” – you can see the pattern here.

And examples of a pattern without a name (that I am aware of) is using succ/2 to count down to 0, then fail. Or use between/3 with forall/2. At some point I was using the name “guards” for this pattern:

p(...) :- some_test, !, ...
p(...) :- another_test, !, ...
p(...) :- yet_another_test, !, ...

… but I think I was confused by something I have read about some other programming language.

The pattern of having a predicate with exactly two clauses, like this:

foo([], ...)
foo([H|T], ...)

is so old and common that it does not need to be named at all I guess?

To keep a short story long, a difference list is the pattern of holding on to a list and to the rest of a list. How exactly you do it shouldn’t matter so much, I think? Like, you could be using a DCG and keep the difference list implicit. Modern Prolog code seems to always use two separate arguments for difference lists? (findall/4, read_line_to_codes/3).

Here, look at this definition of a FIFO queue (stolen, simplified, arguments reordered maybe). My question for you: is there a difference list in here?

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)).
1 Like
3

Thanks for the feedback. :grinning:

For parsing with DCGs when done correctly they are blindingly fast.

Getting back to my view that Prolog is used to create models of problems and then the problem is applied to the model instead of trying to solve the problem directly with Prolog, difference list when thought of as doing pointer manipulation are extremely powerful but sadly it is hard to find good documentation that points this out with graphics. Writing the documentation is on my to-do list but if @dtonhofer needs more convincing I might be doing them sooner rather than latter.

Once place where I saw note of doing pointer manipulation instead of string copies to make the application faster was with NGINX server. Don’t ask for a reference as I must have read about 50 different pages in their documents over the last week and did not keep track of everything I read.

With regards to the queue that looks like code I saw in

Difference Lists by Frank Pfenning on page L11.2

queue(Is) :- q(Is, B\B).
q([enq(X)|Is], F\[X|B]) :- q(Is, F\B).
q([deq(X)|Is], [X|F]\B) :- q(Is, F\B).
q([], []\[]).

will have to check. Also it might be able to be transformed like I did in this example.

4

Funny thing, I just made a small comment about this example in particular. But maybe read my message above to the end and follow the links. I was just trying to say that a difference list is a code pattern, not a particular data structure.

I agree with everything else you wrote.

5

I think they’re easier to understand if you don’t think of them as pointers but instead think of the “holes” as nothing more than logical variables.

?- DiffList = A-X, A = [1,2|X].
DiffList = [1, 2|X]-X,
A = [1, 2|X].

?- DiffList = A-X, A = [1,2|X], X = [3,4].
DiffList = [1, 2, 3, 4]-[3, 4],
A = [1, 2, 3, 4],
X = [3, 4].
2 Likes
6

I guess one important point I completely failed to make is that Difflist = A-X (and similar code) is not a requirement for a difference list, I think (I am starting to dislike the name more and more… I remember struggling with the concept because of the name: it completely sidetracked my thinking…)

Here is some code. I will keep on adding a subgoal, and the question that I have, again, at what moment do we all agree that we have a “difference list” in there?

Step 1

?- L = L0.

Step 2

?- L = L0, L0 = [a|L1].

Step 3

?- L = L0, L0 = [a|L1], L1 = [x,y|L2].

So, is there a “difference list” in Step 1? In Step 2? In Step 3? Is there a difference list at all?

7
Answer

No

8

OK, then we at least got to the bottom of the issue.

Already in Step 1, L and L0 are the base case of a difference list. In Step 2, this is L and L1, in Step 3, it is L and L2. Whether you choose to keep them separate or write them as L-L0 or L\L0 really does not change at all the code pattern.

The code pattern is: you have a list, but you also hold on to the (still uninstantiated) tail of the list.

9

You have

L = L0

Yes separately they could be the base case (tail) for a difference list, e.g.

L.
L0.

I don’t know what you are implying with the unification, e.g.

L = L0.

EDIT

Three ways I use to check if something is a difference list

1). Look at the examples in these test cases and do a mental comparison. Note: Because Discourse doesn’t have an easy way to add an HTML anchor to an expandable section you will have to click on the triangle to see the test cases.

2). Use the Prolog code that checks if a pair is a difference list. Note: Because Discourse doesn’t have an easy way to add an HTML anchor to an expandable section you will have to click on the triangle to see the code.

3). Use write_term/2 with the option dotlists(true) as done in the earlier post and do a mental comparison.

10

I am not implying anything. This is how you make an “empty difference list”. In these examples I have a conjunction, but in real code the three subgoals will be in different calling contexts.

If I rename the variables a bit?

?- List = Rest0, % An empty difference list
    Rest0 = [a|Rest1], % extend the list by one element
    Rest1 = [b|Rest2]. % push another element to the back in constant time
    % at this point List and Rest2 is your difference list
11

OK, I now understand maybe what is going on. I just assumed that you (the programmer) know when you have a difference list. And you are probably doing more complicated things, where you actually want to take a pair of variables and determine whether they form a difference list? This now finally makes sense. I re-read the other thread more carefully, this is all discussed there apparently.

12

The goal of this current round of post related to difference list is to help convince @dtonhofer that accumulator passing uses difference list. It started with this post.

In so doing others will hopefully correct me if I am wrong somewhere, e.g. has_type/2 for difference list and what is a difference list, and help to ensure I am understanding difference list correctly.

When Jan W. has_type/2 for difference list correctly worked with the difference list unit tests I knew I had crossed a significant boundary.

Currently I am doing Visio diagrams with the pointer notation for closed list, open list, difference list and difference list used with accumulator passing. In so doing it makes me think about all of the details upon which I then learn something. If the diagrams work as expected I will post them here. They will be an SVG so that others can view them.

1 Like