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.