How to use difference lists in recursion?

Question

The intent of the following program is as follows clist_d(f(a,f(a,a)),R) the result is a list of all ground arguments, e.g R = [a,a,a]

%Difference list append.
diffapp(X-Y,Y-Z,X-Z). 

%2 base case
clist_d(a,[a]).
clist_d(b,[b]).
clist_d(c,[c]).

%If we get a term f(X,Y) the first term of such list is the element in X,followed by the elements in Y
clist_d(f(X,Y),R) :-
    clist_d(X,R1),
    clist_d(Y,R2),
    diffapp([R1|H]-H,R2-[],R-[]).

%We can also get a g
clist_d(g(X,Y),R) :-
    clist_d(X,R1),
    clist_d(Y,R2),
    diffapp([R1|H]-H,R2-[],R-[]).

However, the program contains a bug. Running the program with the following query:

?- clist_d(f(a,a),R).
R = [[a],a] ?

Produces a bug as you can see above, testing the difference list alone I get the following result

?- X = [a,b,c|T], Y = [1,2,3],diffapp(X-T,Y-[],R-[]).
X = [a,b,c,1,2,3],
T = [1,2,3],
Y = [1,2,3],
R = [a,b,c,1,2,3] ? 
yes

I have made a mistake in my main program, but I can't figure out what to add to make my diffapp work there.

Why? What goal are you trying to reach? You want to find a list with a single atom in it when using clist_d(X,Y)? Why is your tail named H? Why are you using the output list as the head instead of the tail of the list? What queries did you use to get the bottom output? — G_V, Jan 29 '18 at 10:33
Useful resource in understanding difference lists: [Understanding difference lists](https://stackoverflow.com/questions/26966055/understanding-difference-lists) — G_V, Jan 29 '18 at 11:14
*a list of all ground terms, e.g `R = [a,a,a]`*. You actually mean a list of the ground *arguments*. `f(a,a)` is a ground term, `f(a,f(a,a))` is a ground term, etc. `a` is an argument in these cases. Also, is your problem really confined to atoms `a`, `b`, and `c` or do you need to be able to handle, for example `e`? If that's the case, you can generalize the solution Tomas gave by: `clist_d(X,[X|R],R) := atom(X).` — lurker, Jan 29 '18 at 13:38
@lurker You are absolutely right, I mean the list of ground items. Yes, that is correct my program is confined to the atoms a,b,c. I will edit my post to make this more clear for future readers. — JKRT, Jan 29 '18 at 16:21
@G_V H is for mnemonic for hole in this context, I will edit my second query to make it more clear for future readers. — JKRT, Jan 29 '18 at 16:23
@JKT - ah ok, that makes sense. Be aware that [H|T] is the unspoken standard for education about lists, so I personally automatically read it as Head and not Hole. For readability purposes it's better to have descriptive variable names, especially when asking questions about complex topics like this. Example [Learn Prolog Now!](http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse24) — G_V, Jan 30 '18 at 08:09

Tomas By · Accepted Answer · 2018-01-29T18:23:09.580

With difference lists, you want to pass along a pair of arguments everywhere, and you do need any append, so the top-level call should be:

clist_d(f(a,f(a,a)),R,[])

The problem with the nesting in the output is because your base cases return a list (R1), and then in the call to append you cons it ([R1|H]). With no append, that does not happen.

clist_d(f(X,Y),R0,R) :-
  clist_d(X,R0,R1),
  clist_d(Y,R1,R).

clist_d(g(X,Y),R0,R) :-
  clist_d(X,R0,R1),
  clist_d(Y,R1,R).

clist_d(a,[a|R],R).
clist_d(b,[b|R],R).
clist_d(c,[c|R],R).

Produces:

| ?- clist_d(f(a,f(a,a)),R,[]).
R = [a,a,a] ? ;
no

How to use difference lists in recursion?

1 Answers1