What is empty?

This topic was split off (Split Topic) from Module property exported_operators/1 fails instead of returning empty list

This is going a bit off topic (or more to a specific part of the topic) but adding some thoughts/questions regarding when a result should be just success/fail or success/fail with a value.

Granted both you have more experience and skill with Prolog than me, but sitting on the side lines doesn’t advance ones skill.

My thoughts for the last several months on this are that if the code is deterministic and can return a value if successful, then when it fails it should also return a value, e.g [ ].

If the code is non-deterministic, then if it fails it should not return a value, only failure.

Just my thoughts, feel free to ignore or disagree.

1 Like

Roughly I think I can agree. 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.

1 Like


That was a better way to clarify what I am thinking.

Comprehending when this concept is in play and making it work takes an inordinate amount of my time.

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.

1 Like

Thanks, good to see other thoughts.

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. :slightly_smiling_face:


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.


The following are all considered to represent the same list (obviously, they’re different difference lists):


That’s why it’s called a difference list and the L1-L2 notation is used (the “-” is “minus” not “dash”). [Although I have seen people use “/” instead of “-”]

1 Like

I probably don’t understand the problem sorry, but return the value where?

In fact, if it succeeds, the procedure has constrained the variables passed to it partially or completely. But when it fails, any work on that front is released.

Unless one wants to see failure and still retain work done, but that sounds inconsistent.

It was a topic split off from another topic : Module property exported_operators/1 fails instead of returning empty list

Welcome to the world of Discourse.

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.

Any insights on empty for a list of list?

My view is that only [[]] should be allowed?

I don’t understand what you’re saying. [] is the empty list (of anything, including lists). [[]] is not empty; it’s the list with exactly one member: the empty list.



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 [].

1 Like