My notes on difflists

Nice to know
1

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.

Enjoy.

2 Likes
2

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

API documentation: https://logtalk.org/library/difflist_0.html
Source code: https://github.com/LogtalkDotOrg/logtalk3/blob/3bd198125d74191d07c35de7c0d3a86133d0668e/library/types/difflist.lgt

It may provide some answers. Contributions welcome.

1 Like
4

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

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

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.

2 Likes
5

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

6

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.

7

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).
false.