My notes on difflists

I have been Rubber-Duck Debugging about difference lists. I thought I had understood those but then no, and this cycle went on for some time.

Here is some resulting code:

Here is some documentation: Extensive difference list explainer. I have actually my own graphing and vocabulary style for this now, … plus several new questions which I hope to solve eventually.



Related, Logtalk provides a difflist library object, implementing the same protocol defined for the list object:

API documentation:
Source code:

It may provide some answers. Contributions welcome.

1 Like

LOL, I am always amazed at how much that actually works.

I know you have seen our wiki on Difference List, if any of it does not make sense or you think is wrong then please ask, it definitely has room for improvement.

You might find this of value:


and James blog that uses double negation for displaying a difference list that has not been converted to a closed list.

Also I personally find it better to think of the two values representing difference list as pointers rather than list, makes the hand drawings much simpler. Once you have the image drawn, then go back and label the names of the pointers.

1 Like

In your code for computing the length of a difference list, one case you’re missing is:

?- length_dl([1,2,3]-X, Length).

The same exception as in:

?- length_dl(X-Y, Length).
ERROR: Unhandled exception: domain_error(difference_list(overall_structure),_1534-_1536)

would be expected given that you try to check if the first argument is a valid difference list. Your definition also doesn’t (yet?) support a general query such as:

?- length_dl(Difflist, Length).
ERROR: Unhandled exception: domain_error(difference_list(overall_structure),_2296-_2298)

Here, you would want the similar behavior to length/2:

?- difflist::length(Difflist, Length).
Difflist = _3594-_3594,
Length = 0 ;
Difflist = [_4632|_4628]-_4628,
Length = 1 ;
Difflist = [_4632, _5676|_4628]-_4628,
Length = 2 ;
Difflist = [_4632, _5676, _6720|_4628]-_4628,
Length = 3 ...

Keep up the good work.


Thanks Paulo. Your are absolutely right. Something for the TODO stack.

Well, I have updated the whole code.

For some reason, I took me a long while to organize and find a good to think about parameter checking as I wanted to avoid ugly code.

I find the following code:

difference_append(Open_list, Hole, Open_or_closed_list) :-
    Hole = Open_or_closed_list.

I learnt another difference list append, its defining fact reads:

concat(X-Y, Y-Z, X-Z).

Here is are some example runs, the last two queries demonstrate associativity:

?- A = [1, 2|X]-X, B = [3|Y]-Y, concat(A, B, C).
C = [1, 2, 3|Y]-Y.
?- A = [1|X]-X, B = [2|Y]-Y, C = [3|Z]-Z, concat(A, B, H), concat(H, C, D).
D = [1, 2, 3|Z]-Z.
?- A = [1|X]-X, B = [2|Y]-Y, C = [3|Z]-Z, concat(B, C, H), concat(A, H, D).
D = [1, 2, 3|Z]-Z.

What concat/3 cannot do, but append/3 can do, use the first argument twice:

?- A = [1], B = [2], C = [3], append(A, B, D), append(A, C, E).
D = [1, 2],
E = [1, 3].
?- A = [1|X]-X, B = [2|Y]-Y, C = [3|Z]-Z, concat(A, B, D), concat(A, C, E).