Prolog "append_dl/3" wrapper

Question

I am just learning Prolog and the concept of difference-lists in Prolog, so bear with me please.

I have following code:

:- op(400, xfx, \).

append(Xs, Ys, Zs) :-
  append_dl( [Xs|T1]\T1, [Ys|T2]\T2, Zs\[]).

append_dl( Xs\Ys, Ys\Zs, Xs\Zs).

Now if i append Lists [1,2,3] and [a,b,c] in the SWI-interpreter it yields lists of lists

?- append([1,2,3],[a,b,c],Zs).
Zs = [[1, 2, 3], [a, b, c]].

Whereas if i do call append_dl direktly like so:

?- append_dl([1,2,3|T1]\T1,[a,b,c|T2]\T2,Zs\[]).
T1 = [a, b, c],
T2 = [],
Zs = [1, 2, 3, a, b, c].

it works...

What am i doing wrong and how should one wrap these functions using difference lists correctly?

Thank you guys for the Help :D

To your problem.... the issue is that your indirect call to append([1,2,3],[a,b,c],Zs). is actually calling append_dl([[1,2,3]|T1]\T1, [[a,b,c]|T2]\T2, Zs\[]). not append_dl([1,2,3|T1]\T1, [a,b,c|T2]\T2, Zs\[]).. Thus, the inconsistent results. — lurker
Fixing the format of my prior comment... FYI, you don't need to define \ as an operator. The \ is an "older" way of delimiting a difference list. A hyphen (-) is often found in newer literature, e.g., append_dl(Xs-Ys, Ys-Zs, Xs-Zs). — lurker
Seriously: That approach to learning this coding technique leads to nowhere! Rather start using dcgs, and then study the particular encoding of grammar rules. The example is taken from Program 15.2 of the Art of Prolog, but the rule for append/3 is not. It's just fantasy that does not work. — false

false false · Accepted Answer · 2017-11-14T21:05:53

While this programming technique is key to Prolog, this append_dl/3 is an highly artificial example that nobody uses in this precise way. There is a Prolog textbook (Art of Prolog) which uses this as the first "motivating" example and some courses still follow such textbooks literally...

(Let's keep the common definition of append/3 as it is usually defined)

Difference-lists are not lists. Rather, they are differences between lists. So list difference would be a more appropriate name for them. In most situations you do not have such differences ready, rather, you would have to convert an actual list to such a difference or (more commonly) construct the difference while you go along.

So take the list [1,2,3] which can be represented by the difference [1,2,3|Xs]\Xs. Another way to represent it would be [1,2,3]\[]. But you can use append_dl/3 only if the differences are represented in their most general form which you have not. Thus you first need to convert regular lists into that representation.

mappend(XsL, YsL, ZsL) :-
   append(XsL, Xs,Xs0),       % convert XsL to a difference Xs0\Xs
   append(YsL, Ys,Ys0),       % convert YsL to a difference Ys0\Ys
   append_dl( Xs0\Xs, Ys0\Ys, ZsL\[]).

In this concrete example, the conversion was just overhead. You needed the built-in append/3 twice. Also, mappend(XsL, YsL, [1,2]) does not terminate, whereas append(XsL, YsL, [1,2]) does. For that case you would have change the order of the goals.

After you have given in that assignment, I would recommend you study Prolog's dcg notation.

Prolog "append_dl/3" wrapper

1 Answers