Another way to put this is that there are two (main) ways to describe a set : as a multiple solutions to a (thus) non-deterministic predicate or as a list .
This is one of those statements that continue to reverberate in my mind reaching no conclusion.
In thinking about list today I was working with difference list (open list) as opposed to a standard list (closed list) and as we know the base case for a difference list is just a variable and the base case for a closed list is . This just brought a lot of ideas crashing down like a house of cards.
Any thoughts on how to resolve this paradox?
One way that I am thinking to resolve this is that a list can never be used directly. Instead it should be given a type and then only the underlying access to the list can only take place via the predicates that work with the type. I know this sounds a lot like turning Prolog into something it is not, but that is not the point. The point is that it gives one something solid to work with to make progress on the problem.
As I have been learning with Prolog if I start by adding must_be/2 all over the place, as I better understand what is happening, the more I can remove the must_be/2 predicates and the closer the predicates move to pure Prolog. Somewhere along the line if the code is correct, all of the must_be/2 are gone and the solution, not matter how bizarre, is the correct solution.
That’s not a correct description. The difference list equivalent to an empty list is a pair (i.e. a compound term) where both elements are the same variable. Maybe also worth noting that, although the de facto standard representation for a pair uses the (-)/2 infix operator, that’s just a choice. We could use instead e.g. A\A or A+A.
I was thinking of the representation of a difference list as two separate variables and not as a pair joined (-)/2. Examples found here.
One way I can see the use of a difference list as a pair is that the pair is a new type that hides the underlying separate variables. Feel free to disagree with that, that is the point of the discussion.
Thinking more about that I checked the ISO Prolog standard and did not know this, but the standard does have a description of a difference list. Point in your favor.
To denote a stream, we use stream(N, Ll - L2), where
N is the abstract name of the stream (not represented in
the formal specification) and LI - L2 is a difference list
of characters. LI represents the whole contents of the
stream and L2 represents the characters after the pointer
(including the pointed first character). Thus an empty
stream is denoted nil - nil and points on the “eof”. A
stream L - L, L being a non empty list of characters
points on the first character. A stream L - nil points on
the end of file (the current character is “eof”. A stream
A.L - L points on the second and L - A.nil on the last.
Initially a non empty stream pointing on its first element
A will be denoted A. L - A.L.
Another disparity for What is empty? is when a valid answer from a deterministic predicate would be a list of list, e.g. [ [a,b], [1,2], ["Hello","World"] ] where sometimes empty is represented as [] or  or both.
So by that I take it that only  is the correct way to think of what is empty for a list of list. Whether the elements in a list are atoms or other list does not matter, they are still just elements in a list.
Here is a variation that you can correct if it is wrong.
A single level non-empty list would be [ a, b, c] and the empty list would be .
So likewise a list of list would be [ [a,b], [c,d], [e,f] ] and the empty list would be .