prologdifference-lists

Prolog "append_dl/3" wrapper

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

Solution

  • 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 notation.